题目描述

有一个仅由 0 和 1 组成的字符串。对于它的某个子串，如果将 0 和 1 互换（即 0 变 1，1 变 0）并且将字符串倒过来，得到的字符串与原字符串相同，则认为该子串是"反对称"的。例如，子串 01 互换并倒过来是 10，与原串不同；子串 0110 互换并倒过来是 1001，与原串不同；而 0101 互换并倒过来是 1010 还是不同。符合条件的例子：0011 互换并倒过来是 1100 ≠ 0011。等等，实际上"反对称"要求：reverse(s) = invert(s)，其中 invert 将 0 变 1、1 变 0。

给出一个长度为 $N$ 的 01 字符串，请你计算有多少个子串是"反对称"的。

输入格式

第一行一个正整数 $N$。
第二行一个长度为 $N$ 的 01 字符串。

输出格式

一行一个整数，表示"反对称"子串的个数。

样例

8
11001011

7

数据范围

$1 \le N \le 10000$，子串是原字符串中连续的一段。

来源

CodesOnline