E. 二进制字符串游戏

每个测试点的时间限制：$3$ 秒
每个测试点的内存限制：$512$ 兆字节

考虑下面的游戏。两名玩家有一个二进制字符串（由字符 $0$ 和/或 $1$ 组成）。两名玩家轮流操作，第一名玩家先手。在玩家的回合中，他或她必须选择字符串中恰好两个相邻的字符并将其删除（字符串的第一个字符和最后一个字符也被视为相邻的）。此外，根据操作者的不同，还有额外的限制：

• 如果是第一名玩家的回合，所选的两个字符都应为 $0$；
• 如果是第二名玩家的回合，所选的两个字符中至少有一个应为 $1$。

无法进行有效操作的玩家输掉游戏。这也意味着，如果当前字符串长度小于 $2$，当前玩家输掉游戏。

给你一个长度为 $n$ 的二进制字符串 $s$。你需要计算它的子串数量，使得如果在该子串上进行游戏，且双方都采取最优策略，则第一名玩家获胜。换句话说，计算满足 $1 \le l \le r \le n$ 且第一名玩家在字符串 $s_l s_{l+1} \dots s_r$ 上有获胜策略的 $(l, r)$ 对数。

输入
第一行包含一个整数 $n$（$1 \le n \le 3 \cdot 10^5$）。
第二行包含字符串 $s$，长度为 $n$，每个字符为 $0$ 或 $1$。

输出
输出一个整数——使得第一名玩家获胜的子串数量。

示例
输入

10
0010010011

输出

12

注意
在第一个示例中，以下子串对第一名玩家是获胜的（$s[l:r]$ 表示 $s_l s_{l+1} \dots s_r$）：

$s[1:2]$；
$s[1:3]$；
$s[1:7]$；
$s[2:4]$；
$s[2:8]$；
$s[3:5]$；
$s[4:5]$；
$s[4:6]$；
$s[5:7]$；
$s[6:8]$；
$s[7:8]$；
$s[7:9]$。