Cow Protest Partitioning

John's family has n cows that are protesting by standing in a line. The i-th cow has a rationality value \(a_i\). In order to ensure that the cows remain rational during the protest, John wants to divide all the cows into several contiguous groups such that the sum of the rationality values in each group is at least 0. Your task is to compute the maximum number of groups that can be formed following these rules.

inputFormat

The first line contains an integer n indicating the number of cows. The second line contains n space-separated integers \(a_1, a_2, \ldots, a_n\) denoting the rationality values of the cows.

outputFormat

Output a single integer representing the maximum number of contiguous groups such that the sum of the rationality values in each group is at least 0. If no valid partition exists, output 0.

sample

3
1 -2 3

2