Byteasar 正在研究某些由 0 和 1 组成的字符串。设 $x$ 为这样一个字符串。用 $x^R$ 表示 $x$ 的反转字符串（即“倒序读取”），用 $\bar{x}$ 表示将 $x$ 中的所有 0 变为 1、所有 1 变为 0 后得到的字符串。

Byteasar 对反对称性很感兴趣，而对称的事物让他感到厌烦。然而，反对称不仅仅是缺乏对称性。我们称一个（非空）字符串 $x$ 是反对称的，当且仅当对于 $x$ 中的每一个位置 $i$，其倒数第 $i$ 个字符与第 $i$ 个（正数）字符不同。特别地，一个由 0 和 1 组成的字符串 $x$ 是反对称的，当且仅当 $x = {\bar{x}}^R$。例如，字符串 00001111 和 010101 是反对称的，而 1001 则不是。

给定一个由 0 和 1 组成的字符串，我们希望确定其连续非空反对称片段的数量。对应于相同子串的不同片段应被多次计算。

输入格式

第一行包含一个整数 $n$ ($1 \le n \le 500\,000$)，表示字符串的长度。第二行给出一个长度为 $n$ 的由 0 和/或 1 组成的字符串。字符串中没有空格。

输出格式

输出一行，包含一个整数，即给定字符串中连续（非空）反对称片段的数量。

样例

输入 1

8
11001011

输出 1

7

说明 1

反对称片段包括：01（出现两次）、10（出现两次）、0101、1100 和 001011。