#P1584E. Game with Stones
-
ID: 6119
Type: RemoteJudge
2000ms
256MiB
Tried: 0
Accepted: 0
Difficulty: (None)
Uploaded By:
Hydro
Tags> Game with Stones
No submission language available for this problem.
Description
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.
Input
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$.
Output
Print a single integer for each test case — the answer to the problem.
Samples
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
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]$.