Given an array A of lower case characters $$$a_1,a_2,....,a_n$$$ we need to perform the following operation until it becomes empty,

• Select a segment $$$(l,r)$$$ such that $$$a_l=a_{l+1}=a_{l+2}=....=a_r$$$ and remove the segment from the array.

• Add the square of length of segment to your score and rearrange the remaining elements.

Output the maximum score that can be obtained.(score is initialized to 0).

Constraints: n <= 60

input

2
6
a a b b a c
12
a b a b a b a b a b a b

output

14
42