Simple task?

You are given a string $s$, which contains only characters "0" and "1". We call a substring from $l$ to $r$ good if its length is odd, $l<r$ and $s_l=s_r=s_k$ where $k=\frac{l+r}{2}$. You should find the number of good substrings of the string $s$.

Input

The first line contains one integer $n$ ($1\le n\le 10^7$) — the length of the string.

The second line contains $n$ characters $s_1,s_2,\dots ,s_n$ ($s_i\in \{0,1\}$) — the binary string.

Output

Output one number — the amount of good substrings.

Examples

Note

In the first example, any substring with an odd length bigger than $1$ is good: $[1,3]=$"111", $[2,4]=$"111", $[3,5]=$"111", $[1,5]=$"11111".

In the second example, there are only two good substrings: $[1,5]=$"10101" and $[2,6]=$"01010".

Scoring

1. ($3$ points): there are no zeros in the string;

2. ($6$ points): $n\le 100$;

3. ($17$ points): $n\le 10^3$;

4. ($27$ points): the string contains at most $10^3$ ones;

5. ($47$ points): without additional constraints.