题目描述

给定一个长度为 $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 < j$，这次操作是免费的，否则需要花费 $1$ 个硬币。

你需要花费多少个硬币，才能使所有元素都变为 $0$？

输入格式

每组测试数据包含多组测试用例。第一行包含测试用例数量 $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$。

输出格式

对于每组测试用例，输出使所有元素都变为 $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]$。

由 ChatGPT 4.1 翻译

样例

7
4
-3 5 -3 1
2
1 -1
4
-3 2 -3 4
4
-1 1 1 -1
7
-5 7 -6 -4 17 -13 4
6
-1000000000 -1000000000 -1000000000 1000000000 1000000000 1000000000
1
0

3
0
4
1
8
3000000000
0