CF1788E Sum Over Zero

You are given an array $ a_1, a_2, \ldots, a_n $ of $ n $ integers. Consider $ S $ as a set of segments satisfying the following conditions. - Each element of $ S $ should be in form $ [x, y] $ , where $ x $ and $ y $ are integers between $ 1 $ and $ n $ , inclusive, and $ x \leq y $ . - No two segments in $ S $ intersect with each other. Two segments $ [a, b] $ and $ [c, d] $ intersect if and only if there exists an integer $ x $ such that $ a \leq x \leq b $ and $ c \leq x \leq d $ . - For each $ [x, y] $ in $ S $ , $ a_x+a_{x+1}+ \ldots +a_y \geq 0 $ . The length of the segment $ [x, y] $ is defined as $ y-x+1 $ . $ f(S) $ is defined as the sum of the lengths of every element in $ S $ . In a formal way, $ f(S) = \sum_{[x, y] \in S} (y - x + 1) $ . Note that if $ S $ is empty, $ f(S) $ is $ 0 $ . What is the maximum $ f(S) $ among all possible $ S $ ?

The first line contains one integer $ n $ ( $ 1 \leq n \leq 2 \cdot 10^5 $ ). The next line is followed by $ n $ integers $ a_1, a_2, \ldots, a_n $ ( $ -10^9 \leq a_i \leq 10^9 $ ).

Print a single integer, the maximum $ f(S) $ among every possible $ S $ .

In the first example, $ S=\{[1, 2], [4, 5]\} $ can be a possible $ S $ because $ a_1+a_2=0 $ and $ a_4+a_5=1 $ . $ S=\{[1, 4]\} $ can also be a possible solution. Since there does not exist any $ S $ that satisfies $ f(S) > 4 $ , the answer is $ 4 $ . In the second example, $ S=\{[1, 9]\} $ is the only set that satisfies $ f(S)=9 $ . Since every possible $ S $ satisfies $ f(S) \leq 9 $ , the answer is $ 9 $ . In the third example, $ S $ can only be an empty set, so the answer is $ 0 $ .