B. Уничтожение массива
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам дан массив $$$a$$$ из $$$n$$$ целых чисел, таких, что $$$a_1 + a_2 + \cdots + a_n = 0$$$.

За одну операцию можно выбрать два различных индекса $$$i$$$ и $$$j$$$ ($$$1 \le i, j \le n$$$), уменьшить $$$a_i$$$ на единицу и увеличить $$$a_j$$$ на единицу. Если $$$i < j$$$, то эта операция бесплатная, в противном случае она стоит одну монету.

Какое минимальное количество монет нужно потратить, чтобы все элементы стали равны $$$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$$$.

Пример
Входные данные
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
Примечание

Возможная стратегия для первого набора входных данных:

  • Сделаем операцию $$$(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]$$$.