Проста задача?

Вам заданий рядок $s$, який містить лише символи "0" та "1". Ми називаємо підрядок від $l$ до $r$ хорошим, якщо його довжина непарна, $l<r$ та $s_l=s_r=s_k$, де $k=\frac{l+r}{2}$. Вам потрібно знайти кількість хороших підрядків рядка $s$.

Вхідні дані

У першому рядку міститься одне ціле число $n$ ($1\le n\le 10^7$) — довжина рядка.

У другому рядку міститься $n$ символів $s_1,s_2,\dots ,s_n$ ($s_i\in \{0,1\}$) — рядок.

Вихідні дані

Виведіть одне число — кількість хороших підрядків.

Приклади

Примітка

У першому прикладі будь-який підрядок непарної довжини більший за $1$ є хорошим: $[1,3]=$"111", $[2,4]=$"111", $[3,5]=$"111", $[1,5]=$"11111".

У другому прикладі є лише два хороші підрядки: $[1,5]=$"10101" та $[2,6]=$"01010".

Оцінювання

1. ($3$ бали): нема нулів у рядку;

2. ($6$ балів): $n\le 100$;

3. ($17$ балів): $n\le 10^3$;

4. ($27$ балів): рядок містить щонайбільше $10^3$ одиниць;

5. ($47$ балів): без додаткових обмежень.