Given an array of n integers $$$a_1,a_2,...a_n$$$ output the minimum size of the subsequence $$$b = {b_1,b_2,..b_k}$$$ of array a such that the following condition holds

$$$b_1$$$ & $$$b_2$$$ & $$$b_3$$$ &.....& $$$b_k = 0$$$

constraints : 1 <= n <= 1e5, 1 <= $$$a_i$$$ <= 1e4

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