C. Game with Stones
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output
scroll down for answer
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 s1,…,sk
, where si 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 a1,…,an
, 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≤l≤r≤n), such that the sequence al,al+1,…,ar
is winning.
Input
Each test consists of multiple test cases. The first line contains a single integer t
(1≤t≤3⋅105
) — the number of test cases. Description of the test cases follows.
The first line of each test case contains a single integer n
(1≤n≤3⋅105
).
The second line of each test case contains n
integers a1,a2,…,an (0≤ai≤109
).
It is guaranteed that the sum of n
over all test cases does not exceed 3⋅105
.
Output
Print a single integer for each test case — the answer to the problem.
Example
Input
Copy
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
Output
Copy
1
0
4
2
1
3
Note
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].
0 Comments