## MUSIC - Musical Optimization

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 62Output:2

**Explanation**

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.

**Warning: large input/output data, be careful with certain languages**

Added by: | Fudan University Problem Setters |

Date: | 2007-12-03 |

Time limit: | 0.200s |

Source limit: | 50000B |

Memory limit: | 1536MB |

Cluster: | Cube (Intel G860) |

Languages: | All except: C99 ERL JS-RHINO |

Resource: | Lei HUANG [g201513] , used in USACO |