Вам дан массив \(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\)?
Выходные данные
Для каждого набора входных данных выведите минимальное количество монет, которое мы должны потратить, чтобы все элементы равнялись \(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]\).
Примеры
| № | Входные данные | Выходные данные |
|
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
|