P1667 Sequence

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.

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

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

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