CF2070E.Game with Binary String

考虑以下游戏。两个玩家拥有一个二进制字符串（一个由字符 0 和/或 1 组成的字符串）。玩家轮流行动，由第一位玩家先手。在玩家的回合中，必须选择字符串中恰好两个相邻元素并移除它们（首元素和末元素也被视为相邻）。此外，根据当前行动玩家的不同存在额外约束：

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

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

给定一个长度为 $n$ 的二进制字符串 $s$。你需要计算其满足以下条件的子串数量：若在该子串上进行游戏且双方都采取最优决策，第一位玩家将获胜。换句话说，计算满足 $1 \le l \le r \le n$ 的有序对 $(l, r)$ 的数量，使得在字符串 $s_l s_{l+1} \dots s_r$ 上第一位玩家拥有必胜策略。

第一行包含一个整数 $n$（$1 \le n \le 3 \cdot 10^5$）。

第二行包含字符串 $s$，由恰好 $n$ 个字符组成。每个字符为 0 或 1。

输出一个整数——满足条件的子串数量（即第一位玩家能获胜的子串数量）。

第一个示例中，以下子串是第一位玩家的必胜子串（$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]$。

翻译由 DeepSeek R1 完成