Making a Sequence Perfect

You are given a sequence (A) of length (n). A sequence is defined to be perfect if and only if the sum of every contiguous subsequence is positive, i.e. for every pair (1 \le i \le j \le n), (\sum_{k=i}^{j} A_k > 0).

In one operation you are allowed to modify the sequence as follows. Choose an interval ([l, r]) with indices satisfying (1 < l \le r < n) and such that [ S = \sum_{i=l}^{r} A_i < 0. ] Then update the sequence by doing:

[ \begin{cases} A_{l-1} \leftarrow A_{l-1} + S,\ A_{r+1} \leftarrow A_{r+1} + S,\ A_{l} \leftarrow A_{l} - S,\ A_{r} \leftarrow A_{r} - S, \quad \text{if}~l<r,\[1mm] \text{and if}~l = r:\quad A_{l} \leftarrow A_{l} - 2,S. \end{cases} ]

Your task is to determine the minimum number of such operations needed so that the final sequence becomes perfect. If it is impossible to achieve a perfect sequence the answer should be (-1).

Note: Since every contiguous subsequence must have a positive sum, in particular every single element must be positive. Also note that the operation is only allowed on intervals completely inside the boundaries, i.e. the first and last elements (A_1) and (A_n) cannot be directly modified by an operation. You may assume that (n \ge 3) and that initially (A_1 > 0) and (A_n > 0).

inputFormat

The first line contains an integer (n) ( (n \ge 3)).

The second line contains (n) integers (A_1, A_2, \dots, A_n), separated by spaces. It is guaranteed that (A_1 > 0) and (A_n > 0).

outputFormat

Output a single integer — the minimum number of operations required to make the sequence perfect (i.e. every contiguous subarray has a positive sum), or (-1) if it is impossible.

sample

3
3 -1 3

1