Bessie the cow used to write musical melody. A musical melody is represented as a sequence of N (1 <= N <= 100,000) notes numbered 1..N. Note i is represented by the integer A_i (-10,000 <= A_i <= 10,000).

To Bessie's cow-like mind, a musical melody is called 'perfect' if and only if the sum of all the notes in any of its consecutive subsequences is strictly positive.

For a given musical melody, Bessie wants to make it perfect, but she wants to change the melody as little as possible.

Thus, to perfect the melody, she repeatedly chooses a consecutive subsequence of the melody, [x, y] (1 < x <= y < N), whose sum S is negative. Then she adds S to both A_x-1 and A_y+1, while subtracting S from both A_x and A_y. (It is possible to subtract from the same note twice if x = y.)

Given a musical melody, compute the minimum number of steps to make the melody perfect.

Input

* Line 1: The single integer N.

* Lines 2..N+1: Line i+1 contains the single integer A_i.

Output

* Line 1: A single integer that represents the minimum number of steps needed to make the given musical melody perfect. If there are no solutions, output -1 instead.

Example

Input:
5
13
-3
-4
-5
62

Output:
2

There is a musical melody with length of 5. The notes are (13, -3, -4, -5, 62).

First, we choose the range [2, 4]; its sum is (-3) + (-4) + (-5) = -12. After the first step, the melody becomes (1, 9, -4, 7, 50). Second, we choose the range [3, 3], whose sum is -4, and the melody after the second step becomes (1, 5, 4, 3, 50). The melody is perfect now.