数列

题目描述

给定一个长度是 $n$ 的数列 $A$ ,我们称一个数列是完美的,当且仅当对于其任意子段的和都是正的。 现在你有一个操作可以改变数列,选择一个区间 $[l,r]$ 满足 $\sum\limits_{i = l}^r A_i < 0$ ,其中 $1 < l \le r < n$。 令 $S = \sum\limits_{i = l}^r A_i$ ,对于 $A_{l - 1}$ 和 $A_{r + 1}$ 分别加上 $S$,$A_l$ 和 $A_r$ 分别减去 $S$(如果 $l = r$ 就减两次)。问最少几次这样的操作使得最终数列是完美的。

输入输出格式

输入格式


第 $1$ 行一个数 $n$ ,以下 $n$ 个数。 第 $2$ 行至第 $n + 1$ 行,第 $i$ 行一个数 $A_i$。

输出格式


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

输入输出样例

输入样例 #1

5
13
-3 
-4
-5
62

输出样例 #1

2

说明

### 样例解释 首先选择区间 $[2,4]$,之后数列变成 $1,9-4,7,50$,然后选择 $[3,3]$,数列变成 $1,5,4,3,50$ ### 限制与约定 对于 $20\%$ 的数据,满足 $1 \le N \le 5$ ; 对于 $100\%$ 的数据,满足 $1 \le N \le 10^5$ ; $1 \le |A_i| < 2^{31}$