考虑以下游戏。两个玩家有一个二进制字符串(由字符组成的字符串 0 和/或 1)。玩家轮流进行,第一个玩家先进行第一个回合。在玩家的回合中,他或她必须选择字符串中两个相邻的元素并将它们删除(第一个元素和最后一个元素也被认为是相邻的)。此外,根据谁采取行动,还有其他限制:
- 如果是第一个玩家的举动, 两者 选择的字符应该是 0;
- 如果是第二个玩家的举动, 至少一个 所选字符的 应该是 1.
无法做出有效动作的玩家输掉游戏。这也意味着如果字符串当前少于 $$$2$$$ 个字符,则当前玩家输掉游戏。
给你一个长度为$$$n$$$的二进制字符串$$$s$$$。您必须计算其子串的数量,这样,如果在该子串上进行游戏并且两个玩家都做出最佳决策,则第一个玩家获胜。换句话说,计算 $$$(l, r)$$$ 的对数,使得 $$$1 \le l \le r \le n$$$ 并且第一个玩家在字符串 $$$s_l s_{l+1} \dots s_r$$$ 上有获胜策略。
输入
第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 3 \cdot 10^5$$$)。
第二行包含字符串 $$$s$$$,由 $$$n$$$ 个字符组成。字符串的每个字符都是 0 or 1.
输出
打印一个整数 - 子串的数量,如果在该子串上进行游戏,则第一个玩家获胜。
示例
输入复制
100010010011
输出复制
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]$$$。