H. Maximum Beauty
time limit per test
1 second
memory limit per test
512 megabytes
input
standard input
output
standard output

Let's denote the beauty of a string as follows: consider the lengths of all maximal contiguous blocks consisting of the same letters. Then, the beauty of a string is the sum of the squares of the lengths of all such blocks.

For example, let the string be "aabbbcaaadddd". In this string, the following blocks of identical letters exist: a block of two letters "a", a block of three letters "b", a block of one letter "c", a block of three letters "a", and a block of four letters "d". Thus, the beauty of this string is $$$2^2 + 3^2 + 1^2 + 3^2 + 4^2 = 4 + 9 + 1 + 9 + 16 = 39$$$.

Monocarp has a string $$$s$$$, consisting of $$$n$$$ lowercase Latin letters. He will perform the following action exactly once: choose a pair of adjacent different letters in the string $$$s$$$ and swap them.

Your task is to determine the maximum beauty of the new string that Monocarp can obtain after exactly one swap of adjacent different letters in his string $$$s$$$.

Input

The first line contains an integer $$$n$$$ ($$$2 \le n \le 200\,000$$$) — the length of the string $$$s$$$.

The second line contains the string $$$s$$$ of length $$$n$$$, consisting of lowercase Latin letters.

Additional constraint on the input:

  • there are at least two different letters in the given string.
Output

Output the maximum beauty of the new string that Monocarp can obtain after exactly one swap of adjacent different letters in his string $$$s$$$.

Examples
Input
11
aabaacaabaa
Output
21
Input
5
wwwwz
Output
11
Note

In the first example, for example, it is possible to swap the third and fourth letters. Then Monocarp will get the string "aaabacaabaa". The beauty of this string is $$$3^2 + 1^2 + 1^2 + 1^2 + 2^2 + 1^2 + 2^2 = 9 + 1 + 1 + 1 + 4 + 1 + 4 = 21$$$.

In the second example, it is possible to swap the fourth and fifth letters. Then Monocarp will get the string "wwwzw". The beauty of this string is $$$3^2 + 1^2 + 1^2 = 9 + 1 + 1 = 11$$$.