Consistency Score

Find the longest contiguous segment such that the sum of every non-empty prefix starting from its left end is at least 0. Output 0 if there is no valid non-empty segment.

输入格式

The first line contains n (1..100000), and the second line contains n integers (−10⁹..10⁹). The problem definition includes no extra parameter k.

输出格式

Output a single integer, the answer required by the problem.

样例 1

输入：

5
1 1 2 3 1

输出：

5

样例 2

输入：

2
-1 -2

输出：

0

样例 3

输入：

3
1 -2 3

输出：

1

样例说明

Example 1: the prefix sums of the whole array are 1, 2, 4, 7, 8, all non-negative, so the length is 5. Example 2: every segment starts with a negative element, so the answer is 0. Example 3: the second prefix of [1,−2] is −1, and the first prefix of [−2,3] is −2, so only the single element 1 or 3 can be taken, and the answer is 1.