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 < 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 $ ?

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 $ .

For each test case, print the minimum number of coins we have to spend in order to make all elements equal to $ 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] $ .