#P1667. 数列

数列

题目描述

给定一个长度是 nn 的数列 AA ,我们称一个数列是完美的,当且仅当对于其任意连续子序列的和都是正的。

现在你有一个操作可以改变数列,选择一个区间 [l,r][l,r] 满足 i=lrAi<0\sum\limits_{i = l}^r A_i < 0 ,其中 1<lr<n1 < l \le r < n

S=i=lrAiS = \sum\limits_{i = l}^r A_i ,对于 Al1A_{l - 1}Ar+1A_{r + 1} 分别加上 SSAlA_lArA_r 分别减去 SS(如果 l=rl = r 就减两次)。问最少几次这样的操作使得最终数列是完美的。

输入格式

11 行一个数 nn ,以下 nn 个数。

22 行至第 n+1n + 1 行,第 ii 行一个数 AiA_i

输出格式

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

5
13
-3 
-4
-5
62
2

提示

样例解释

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

限制与约定

对于 20%20\% 的数据,满足 1N51 \le N \le 5 ;

对于 100%100\% 的数据,满足 1N1051 \le N \le 10^5 ; 1Ai<2311 \le |A_i| < 2^{31}