【题目描述】

给定一个长度是n的数列A,我们称一个数列是完美的,当且仅当对于其任意连续子序列的和都是正的。现在你有一个操作可以改变数列,选择一个区间[x,y]满足A(x)+A(x+1)+…+A(y)<0,l<X≤Y<n,令S=A(x)+A(x+1)+…+A(y),对于A(x-1)和A(y+1)分别加上S,Ax和Ay分别减去S(如果X=Y就减两次)。问最少几次这样的操作使得最终数列是完美的。

【输入文件】

第一行一个数n,以下n个数。

【输出文件】

一个数表示最少的操作次数,如果无解输出-l。

【样例输入】

5
13
-3
-4
-5
62

【样例输出】

2

【样例解释】

首先选择区间[2,4],之后数列变成1,9,-4,7,50,然后选择[3,3],数列变成1,5,4,3,50

【数据规模】

对于20％的数据,满足1≤N≤5；

对干l00％的数据。满足1≤N≤10^5；1≤|A[i]|≤2^31-1。