Description

Given a sequence $A$ of length $n$, we call a sequence "perfect" if and only if the sum of any of its subarrays is positive.

You have an operation that can modify the sequence: choose an interval $[l,r]$ satisfying $\sum\limits_{i = l}^r A_i < 0$, where $1 < l \le r < n$.

Let $S = \sum\limits_{i = l}^r A_i$. Add $S$ to $A_{l - 1}$ and $A_{r + 1}$, and subtract $S$ from $A_l$ and $A_r$ (if $l = r$, subtract twice). Find the minimum number of such operations needed to make the sequence perfect.

Input Format

The first line contains an integer $n$.

Lines $2$ through $n + 1$: the $i$-th line contains an integer $A_i$.

Output Format

Output a single integer: the minimum number of operations. If there is no solution, output $-1$.

5
13
-3 
-4
-5
62

2

Hint

Sample explanation:

First choose the interval $[2,4]$, then the sequence becomes $1,9,-4,7,50$. Then choose $[3,3]$, the sequence becomes $1,5,4,3,50$.

Constraints:

• For $20\%$ of the testdata, $1 \le n \le 5$.
• For $100\%$ of the testdata, $1 \le n \le 10^5$; $1 \le |A_i| < 2^{31}$.

Translated by ChatGPT 5