Вам дан массив \(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
1000 ms 256 Mb Правила оформления программ и список ошибок при автоматической проверке задач