H. Максимальная красота
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Введем понятие красоты строки. Рассмотрим длины всех максимальных по включению блоков, состоящих из одинаковых букв. Тогда красота строки — это сумма квадратов длин всех таких блоков.

Например, пусть строка равна «aabbbcaaadddd». В этой строке следующие блоки одинаковых букв: блок из двух букв «a», блок из трех букв «b», блок из одной буквы «c», блок из трех букв «a» и блок из четырех букв «d». Таким образом, красота этой строки равна $$$2^2 + 3^2 + 1^2 + 3^2 + 4^2 = 4 + 9 + 1 + 9 + 16 = 39$$$.

У Монокарпа есть строка $$$s$$$, состоящая из $$$n$$$ букв латинского алфавита. Он ровно один раз выберет пару соседних различных букв в строке $$$s$$$ и поменяет их местами.

Перед вами стоит задача определить максимальную красоту новой строки Монокарпа, которую он может получить после ровно одного обмена соседних различных букв в своей строке $$$s$$$.

Входные данные

В первой строке следует целое число $$$n$$$ ($$$2 \le n \le 200\,000$$$) — длина строки $$$s$$$.

Во второй строке следует строка $$$s$$$ длины $$$n$$$, состоящая из строчных букв латинского алфавита.

Дополнительное ограничение на входные данные:

  • в строке есть хотя бы две различные буквы.
Выходные данные

Выведите максимальную красоту новой строки, которую Монокарп может получить после ровно одного обмена соседних различных букв в своей строке $$$s$$$.

Примеры
Входные данные
11
aabaacaabaa
Выходные данные
21
Входные данные
5
wwwwz
Выходные данные
11
Примечание

В первом примере можно, например, поменять местами третью и четвертую буквы. Тогда Монокарп получит строку «aaabacaabaa». Красота этой строки равна $$$3^2 + 1^2 + 1^2 + 1^2 + 2^2 + 1^2 + 2^2 = 9 + 1 + 1 + 1 + 4 + 1 + 4 = 21$$$.

Во втором примере нужно поменять местами четвертую и пятую буквы. Тогда Монокарп получит строку «wwwzw». Красота этой строки равна $$$3^2 + 1^2 + 1^2 = 9 + 1 + 1 = 11$$$.