CF1405B.Array Cancellation

You're given an array $a$ of $n$ integers, such that $a_1 + a_2 + \cdots + a_n = 0$.

In one operation, you can choose two different indices $i$ and $j$ ($1 \le i, j \le n$), decrement $a_i$ by one and increment $a_j$ by one. If $i \lt j$ this operation is free, otherwise it costs one coin.

How many coins do you have to spend in order to make all elements equal to $0$?

给你一个包含 $n$ 个整数的数组 $a$，满足 $a_1 + a_2 + \cdots + a_n = 0$。

一次操作中，你可以选择两个不同的下标 $i$ 和 $j$（$1 \le i, j \le n$），将 $a_i$ 减 $1$，同时将 $a_j$ 加 $1$。若 $i \lt j$，该操作免费；否则（即 $i > j$）需花费一枚硬币。

为使数组所有元素均变为 $0$，你至少需要花费多少枚硬币？

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 5000$). Description of the test cases follows.

The first line of each test case contains an integer $n$ ($1 \le n \le 10^5$) — the number of elements.

The next line contains $n$ integers $a_1, \ldots, a_n$ ($-10^9 \le a_i \le 10^9$). It is given that $\sum_{i=1}^n a_i = 0$.

It is guaranteed that the sum of $n$ over all test cases does not exceed $10^5$.

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$（$1 \le t \le 5000$）。随后是测试用例的描述。

每个测试用例的第一行包含一个整数 $n$（$1 \le n \le 10^5$）—— 元素个数。

下一行包含 $n$ 个整数 $a_1, \ldots, a_n$（$-10^9 \le a_i \le 10^9$）。已知 $\sum_{i=1}^n a_i = 0$。

保证所有测试用例的 $n$ 之和不超过 $10^5$。

For each test case, print the minimum number of coins we have to spend in order to make all elements equal to $0$.

对于每个测试用例，输出使所有元素变为 $0$ 所需花费的最少硬币数量。

Possible strategy for the first test case:

• Do $(i=2, j=3)$ three times (free), $a = [-3, 2, 0, 1]$.
• Do $(i=2, j=1)$ two times (pay two coins), $a = [-1, 0, 0, 1]$.
• Do $(i=4, j=1)$ one time (pay one coin), $a = [0, 0, 0, 0]$.

第一个测试用例的可能策略：

• 执行 $(i=2, j=3)$ 三次（免费），$a = [-3, 2, 0, 1]$。
• 执行 $(i=2, j=1)$ 两次（支付两枚硬币），$a = [-1, 0, 0, 1]$。
• 执行 $(i=4, j=1)$ 一次（支付一枚硬币），$a = [0, 0, 0, 0]$。