Doraemon's Quest: Minimum Initial Health

Doraemon is off on a quest to fight dragons and monsters! He must traverse \(n\) levels. In each level, he either encounters a monster, which decreases his health by a certain amount, or a camp, which increases his health.

At any moment in his journey, Doraemon's health must remain above \(0\). Given that health values are positive integers, determine the minimum initial health Doraemon must have to complete all the levels successfully.

The health change for each level is given as an integer \(a_i\), where a negative value indicates a loss (monster fight) and a positive value indicates a gain (camp). Formally, if Doraemon starts with an initial health \(H\) and traverses the levels sequentially, letting \(S_k = \sum_{i=1}^{k} a_i\) be the cumulative change after level \(k\), then we require:

\[ H + S_k > 0, \quad \text{for all } 1 \le k \le n. \]

Find the minimum \(H\) meeting these conditions.

inputFormat

The first line contains a single integer \(n\) (the number of levels).

The second line contains \(n\) space-separated integers \(a_1, a_2, \ldots, a_n\), where each \(a_i\) represents the health change at the \(i\)-th level (negative for a monster fight and positive for a camp).

outputFormat

Output a single integer, the minimum initial health required such that Doraemon's health remains greater than \(0\) throughout his journey.

sample

5
-3 2 -3 4 1

5