该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

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

12

样例解释

在样例 $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$。