题目描述
给定一个长度是 n 的数列 A ,我们称一个数列是完美的,当且仅当对于其任意连续子序列的和都是正的。
现在你有一个操作可以改变数列,选择一个区间 [l,r] 满足 i=l∑rAi<0 ,其中 1<l≤r<n。
令 S=i=l∑rAi ,对于 Al−1 和 Ar+1 分别加上 S,Al 和 Ar 分别减去 S(如果 l=r 就减两次)。问最少几次这样的操作使得最终数列是完美的。
输入格式
第 1 行一个数 n ,以下 n 个数。
第 2 行至第 n+1 行,第 i 行一个数 Ai。
输出格式
一个数表示最少的操作次数,如果无解输出 −1。
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 ;
对于 100% 的数据,满足 1≤N≤105 ; 1≤∣Ai∣<231