C. Alpha Beta
time limit per test
1 second
memory limit per test
512 megabytes
input
standard input
output
standard output

Let $$$S$$$ be a string consisting of lowercase English letters of length $$$n$$$. We want to partition $$$S$$$ into 26 sets $$$s_1, s_2, s_3, \ldots, s_{26}$$$, where each set $$$s_i$$$ represents a set of indices $$$j$$$ such that $$$S[j]$$$ is the $$$i$$$-th letter of the English alphabet ('$$$a$$$' to '$$$z$$$').

For example: Set $$$s_1$$$ contains indices $$$j$$$ ($$$1 \leq j \leq |S|$$$) where $$$S[j] = $$$ '$$$a$$$'. If $$$S = $$$ "$$$aabca$$$", then the value of $$$s_1$$$ can be $$$\{\}$$$, $$$\{1\}$$$, $$$\{2\}$$$, $$$\{5\}$$$, $$$\{1, 2\}$$$, $$$\{1, 5\}$$$, $$$\{2, 5\}$$$, or $$$\{1, 2, 5\}$$$.

The partition is considered "good" if the following two conditions are satisfied:

  • Each set $$$s_i$$$ is non-empty, i.e., $$$|s_i| \gt 0$$$ for all $$$i = 1, 2, \ldots, 26$$$.
  • For every pair of adjacent sets $$$s_i$$$ and $$$s_{i+1}$$$, all the indices in $$$s_{i+1}$$$ come after all the indices in $$$s_{i}$$$. Formally: $$$$$$\max_{x \in s_i} x \lt \min_{y \in s_{i+1}} y, \quad \forall i = 1, 2, \ldots, 25$$$$$$

The value of a good partition is: $$$$$$\sum_{i=1}^{25} \sum_{j=i+1}^{26} (|s_i| + |s_j|)^2$$$$$$ where $$$|s_i|$$$ denotes the cardinality (size) of the set $$$s_i$$$.

Your task is to find the maximum value among all possible good partitions of the given string $$$S$$$.

Input

A single line contains an integer $$$n$$$ ($$$1 \leq n \leq 2000$$$) denoting the length of the string $$$S$$$.

The next line contains the string $$$S$$$ consisting of $$$n$$$ lowercase English letters.

Output

For each test case, print the maximum value of a good partition of $$$S$$$. If there are no good partitions, output 0.

Examples
Input
26
abcdefghijklmnopqrstuvwxyz
Output
1300
Input
29
abaaacdefghijklmnopqrstuvwxyz
Output
1300
Input
30
abbaaacdefghijklmnopqrstuvwxyz
Output
1425
Input
4
abcd
Output
0
Note

For the second test case:

The only good partition is, $$$s_1 = \{1\}, s_2 = \{2\}, s_3 = \{6\}, s_4 = \{7\}, \ldots, s_{25} = \{28\}, s_{26} = \{29\}$$$. The value of this partition is $$$\sum_{i=1}^{25} \sum_{j=i+1}^{26} (1 + 1)^2 = 325 \cdot 4 = 1300$$$.