D. 果园争锋

题目描述

两名果农在一条果园带上竞争。果园带上 $n$ 棵果树排成一排，每棵树状态为未成熟（标记为 $0$ ）或成熟（标记为 $1$ ）。两人轮流行动，果农 $1$ 先开始。

每回合行动规则：

果农 $1$ ：必须选择两棵相邻且均未成熟的果树（ $00$ ），将其移出果园。
果农 $2$ ：必须选择两棵相邻果树中至少一棵已成熟的果树（ $01$ 、 $10$ 或 $11$ ），将其移出果园。

若某个果农无法按规则行动（包括剩余果树少于 2 棵），则认定该果农败北。

任务：

给定果园初始状态序列 $s$ （例如 “ $0110$ ”），请计算所有连续果树段（子串）中，果农 $1$ 在双方最优策略下必胜的片段数量。

输入格式

第一行输入一个整数 $n$ 代表果树数量。

第二行输入一个长度为 $n$ 的字符串 $s$ 代表果树是否成熟。每一个字符都是 $0$ 或者 $1$ 。

输出格式

输出一个整数，代表能让果农 $1$ 获得胜利的连续果树段数量。

样例输入1

10
0010010011

样例输出1

样例解释

在样例 $1$ 里面，以下的果树段能让玩家 $1$ 获胜。( $s[l, r]$ 代表 $s_ls_{l + 1}\ldots 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]$ 。

数据范围

对于 $10\%$ 的数据， $n \le 10$ 。
对于 $50\%$ 的数据， $n \le 10^3$ 。
对于 $100\%$ 的数据， $n \le 3 \times 10^5$ 。