题目描述

给定一个只包含字符 0 和 1 的字符串 $s$。

若一个从 $l$ 到 $r$ 的子串满足以下条件，则称它为好子串：

• 子串长度为奇数；
• $l<r$；
• $s_l=s_r=s_k$，其中 $k=\frac{l+r}{2}$。

请你求字符串 $s$ 中好子串的数量。

输入格式

第一行包含一个整数 $n$，表示字符串长度。

第二行包含 $n$ 个字符 $s_1,s_2,\dots,s_n$，组成二进制字符串。

输出格式

输出一个整数，表示好子串的数量。

数据范围

$1\le n\le 10^7$。

$s_i\in\{0,1\}$。

输入输出样例 #1

输入 #1

5
11111

输出 #1

4

评分方式