Directional Increase
Contest: Codeforces Round 800 (Div. 1)
Difficulty rating: 1300
Tags: greedy

We have an array of length $$$n$$$. Initially, each element is equal to $$$0$$$ and there is a pointer located on the first element.

We can do the following two kinds of operations any number of times (possibly zero) in any order:

1. If the pointer is not on the last element, increase the element the pointer is currently on by $$$1$$$. Then move it to the next element.
2. If the pointer is not on the first element, decrease the element the pointer is currently on by $$$1$$$. Then move it to the previous element.

But there is one additional rule. After we are done, the pointer has to be on the first element.

You are given an array $$$a$$$. Determine whether it's possible to obtain $$$a$$$ after some operations or not.

Input format:
The first line contains a single integer $$$t$$$ $$$(1\le t\le 1000)$$$  — the number of test cases. The description of the test cases follows.

The first line of each test case contains a single integer $$$n$$$ $$$(1\le n\le 2 \cdot 10^5)$$$  — the size of array $$$a$$$.

The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$-10^9 \le a_i \le 10^9$$$) — elements of the array.

It is guaranteed that the sum of $$$n$$$ over all test cases doesn't exceed $$$2 \cdot 10^5$$$.

Output format:
For each test case, print "Yes" (without quotes) if it's possible to obtain $$$a$$$ after some operations, and "No" (without quotes) otherwise.

You can output "Yes" and "No" in any case (for example, strings "yEs", "yes" and "Yes" will be recognized as a positive response).

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
In the first test case we can obtain the array after some operations, but the pointer won't be on the first element.

One way of obtaining the array in the second test case is shown below.

$$$\langle \underline{0}, 0, 0, 0\rangle \to \langle 1, \underline{0}, 0, 0 \rangle \to \langle \underline{1}, -1, 0, 0\rangle \to \langle 2, \underline{-1}, 0, 0\rangle \to \langle 2, 0, \underline{0}, 0\rangle \to \langle 2, \underline{0}, -1, 0\rangle \to \langle \underline{2}, -1, -1, 0\rangle$$$

Example input:
7
2
1 0
4
2 -1 -1 0
4
1 -4 3 0
4
1 -1 1 -1
5
1 2 3 4 -10
7
2 -1 1 -2 0 0 0
1
0

Example output:
No
Yes
No
No
Yes
Yes
Yes

Editorial:
First of all the sum of the elements has to be $$$0$$$ because the pointer has to end up on the first element.
Denote the number of times you do the first operation while the pointer is on the $$$i$$$-th element as $$$b_i$$$. And the number of times you do the second operation while the pointer is on the $$$i$$$-th element as $$$c_i$$$.
$$$a_i = b_i - c_i$$$ and $$$c_i = b_{i - 1}$$$ because the pointer has to end up on the first element.
So $$$a_i = b_i - b_{i - 1} \to b_i = a_i + b_{i - 1}$$$ and $$$b_1 = a_1$$$.
Now that we have calculated $$$b$$$, we need to determine whether it's possible to perform the operations like so.
There are two conditions.
• $$$b_i \geq 0$$$ ($$$1 \leq i \leq n$$$).
• If $$$b_i = 0$$$ for each $$$j$$$, $$$i < j$$$, $$$b_j = 0$$$. Because the pointer couldn't reach the $$$j$$$-th element.
You can always construct $$$a$$$ if these two conditions hold.
Proof by induction. Perform the first operation and the second operation $$$b_1 - 1$$$ times in a row. Then perform the first operation. Construct the rest by induction and then perform the second operation.
Time complexity: $$$\mathcal{O}(n)$$$