← 返回题目列表

Codeforces · 1584/E

E. 石头游戏

中文机器翻译题面 查看原题

Bob 决定暂时放下微积分作业,为自己设计一个游戏。

游戏是在一系列石子上进行的,可以用整数序列 $$$s_1, \ldots, s_k$$$ 来描述,其中 $$$s_i$$$ 是第 $$$i$$$ 堆中石子的数量。在每一回合中,鲍勃都会挑选一对非空的相邻堆 $$$i$$$ 和 $$$i+1$$$,并从每个堆中取出一颗石头。如果一堆变空,则其相邻的堆不会变得相邻。当鲍勃不能再轮流时,游戏结束。如果最后所有的堆都是空的,鲍勃就认为自己是赢家。

如果鲍勃可以从一系列的牌开始,并通过一些动作序列获胜,我们就会考虑获胜的一系列牌堆。

给定一个序列 $$$a_1, \ldots, a_n$$$,计算 $$$a$$$ 描述获胜牌堆序列的子段数。换句话说,找到段数 $$$[l, r]$$$ ($$$1 \leq l \leq r \leq n$$$),使得序列 $$$a_l, a_{l+1}, \ldots, a_r$$$ 获胜。

输入

每个测试由多个测试用例组成。第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 3 \cdot 10^5$$$) — 测试用例的数量。测试用例的描述如下。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \leq n \leq 3 \cdot 10^5$$$)。

每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \leq a_i \leq 10^9$$$)。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$3 \cdot 10^5$$$。

输出

为每个测试用例打印一个整数——问题的答案。

示例

输入 #1

6
2
2 2
3
1 2 3
4
1 1 1 1
4
1 2 2 1
4
1 2 1 2
8
1 2 1 2 1 2 1 2

输出 #1

1
0
4
2
1
3

注意

在第一个测试用例中,Bob 无法在长度为 $$$1$$$ 的子段上获胜,因为长度为 $$$1$$$ 的数组中没有一对相邻的桩。

在第二个测试用例中,每个子段都没有获胜。

在第四个测试用例中,子段 $$$[1, 4]$$$ 获胜,因为 Bob 可以对相邻桩对进行移动:$$$(2, 3)$$$、$$$(1, 2)$$$、$$$(3, 4)$$$。另一个获胜的子部分是$$$[2, 3]$$$。