Game with Stones

题意翻译

给定一个长度为 $n$ 的序列 $a_i$，现在问其中有多少个子段，满足存在一种方案，每次使相邻的两个数减一，可以使得所有数变为 $0$。 $1\le n\le 3\times 10^5$，$0\le a_i\le 10^9$。

题目描述

Bob decided to take a break from calculus homework and designed a game for himself. The game is played on a sequence of piles of stones, which can be described with a sequence of integers $ s_1, \ldots, s_k $ , where $ s_i $ is the number of stones in the $ i $ -th pile. On each turn, Bob picks a pair of non-empty adjacent piles $ i $ and $ i+1 $ and takes one stone from each. If a pile becomes empty, its adjacent piles do not become adjacent. The game ends when Bob can't make turns anymore. Bob considers himself a winner if at the end all piles are empty. We consider a sequence of piles winning if Bob can start with it and win with some sequence of moves. You are given a sequence $ a_1, \ldots, a_n $ , count the number of subsegments of $ a $ that describe a winning sequence of piles. In other words find the number of segments $ [l, r] $ ( $ 1 \leq l \leq r \leq n $ ), such that the sequence $ a_l, a_{l+1}, \ldots, a_r $ is winning.

输入输出格式

输入格式

Each test consists of multiple test cases. The first line contains a single integer $ t $ ( $ 1 \leq t \leq 3 \cdot 10^5 $ ) — the number of test cases. Description of the test cases follows. The first line of each test case contains a single integer $ n $ ( $ 1 \leq n \leq 3 \cdot 10^5 $ ). The second line of each test case contains $ n $ integers $ a_1, a_2, \ldots, a_n $ ( $ 0 \leq a_i \leq 10^9 $ ). It is guaranteed that the sum of $ n $ over all test cases does not exceed $ 3 \cdot 10^5 $ .

输出格式

Print a single integer for each test case — the answer to the problem.

输入输出样例

输入样例 #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

说明

In the first test case, Bob can't win on subsegments of length $ 1 $ , as there is no pair of adjacent piles in an array of length $ 1 $ . In the second test case, every subsegment is not winning. In the fourth test case, the subsegment $ [1, 4] $ is winning, because Bob can make moves with pairs of adjacent piles: $ (2, 3) $ , $ (1, 2) $ , $ (3, 4) $ . Another winning subsegment is $ [2, 3] $ .