D. AB-строка
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Строка $$$t_1t_2 \dots t_k$$$ является хорошей, если каждый символ этой строки принадлежит хотя бы одному палиндрому длины больше 1.

Палиндром — это строка, читающаяся одинаково от первого символа к последнему и от последнего символа к первому. Например, строки A, BAB, ABBA, BAABBBAAB являются палиндромами, а строки AB, ABBBAA, BBBA — нет.

Например, хорошим являются строки:

  • $$$t$$$ = AABBB (символы $$$t_1$$$, $$$t_2$$$ принадлежат палиндрому $$$t_1 \dots t_2$$$, а символы $$$t_3$$$, $$$t_4$$$, $$$t_5$$$ — палиндрому $$$t_3 \dots t_5$$$);
  • $$$t$$$ = ABAA (символы $$$t_1$$$, $$$t_2$$$, $$$t_3$$$ принадлежат палиндрому $$$t_1 \dots t_3$$$, а символ $$$t_4$$$ — палиндрому $$$t_3 \dots t_4$$$);
  • $$$t$$$ = AAAAA (все символы принадлежат палиндрому $$$t_1 \dots t_5$$$);

Вам задана строка $$$s$$$ длины $$$n$$$, состоящая только из букв A и B.

Посчитайте количество хороших подстрок строки $$$s$$$.

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

Первая строка содержит число $$$n$$$ ($$$1 \le n \le 3 \cdot 10^5$$$) — длину строки $$$s$$$.

Вторая строка содержит строку $$$s$$$, состоящую из букв A и B.

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

Выведите одно число — количество хороших подстрок строки $$$s$$$.

Примеры
Входные данные
5
AABBB
Выходные данные
6
Входные данные
3
AAA
Выходные данные
3
Входные данные
7
AAABABB
Выходные данные
15
Примечание

Первая строка содержит шесть хороших подстрок: $$$s_1 \dots s_2$$$, $$$s_1 \dots s_4$$$, $$$s_1 \dots s_5$$$, $$$s_3 \dots s_4$$$, $$$s_3 \dots s_5$$$ и $$$s_4 \dots s_5$$$.

Вторая строка содержит две хороших подстроки: $$$s_1 \dots s_2$$$, $$$s_1 \dots s_3$$$ and $$$s_2 \dots s_3$$$