CF1584E Game with Stones

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.

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] $ .