Pak Chanek 正在参加 lemper 烹饪比赛。在比赛中,Pak Chanek 必须用 $$$N$$$ 炉子烹饪 lempers,这些炉子从炉子 $$$1$$$ 到炉子 $$$N$$$ 依次排列。最初,炉子 $$$i$$$ 的温度为 $$$A_i$$$ 度。炉子可能具有负温度。
Pak Chanek 意识到,为了烹饪他的 lempers,他需要将每个炉子的温度保持在非负值。为了实现这一目标,Pak Chanek 可以执行零次或多次操作。在一次操作中,Pak Chanek 选择一个炉子 $$$i$$$,其中 $$$2 \leq i \leq N-1$$$,然后:
1. 将炉灶温度 $$$i-1$$$ 更改为 $$$A_{i-1} := A_{i-1} + A_{i}$$$,
2. 将炉子 $$$i+1$$$ 的温度更改为 $$$A_{i+1} := A_{i+1} + A_{i}$$$,并且
3. 将炉灶温度 $$$i$$$ 更改为 $$$A_i := -A_i$$$。
Pak Chanek 想知道他需要执行的最少操作次数,才能使所有炉子的温度都处于非负值。帮助 Pak Chanek 告诉他所需的最少手术次数,或者在无法完成的情况下报告。
输入
第一行包含一个整数 $$$N$$$ ($$$1 \le N \le 10^5$$$) — 炉灶的数量。
第二行包含 $$$N$$$ 整数 $$$A_1, A_2, \ldots, A_N$$$ ($$$-10^9 \leq A_i \leq 10^9$$$) — 炉子的初始温度。
输出
输出一个整数,表示使所有炉子的温度达到非负值所需的最少操作次数,如果不可能,则输出 $$$-1$$$。
示例
输入 #1
7 2 -1 -1 5 2 -2 9
输出 #1
4
输入 #2
5 -1 -2 -3 -4 -5
输出 #2
-1
注意
对于第一个示例,可以完成的操作顺序如下:
- Pak Chanek 执行了一个操作来炉子 $$$3$$$,$$$A = [2, -2, 1, 4, 2, -2, 9]$$$。
- Pak Chanek 执行了一个操作来加热 $$$2$$$,$$$A = [0, 2, -1, 4, 2, -2, 9]$$$。
- Pak Chanek 执行了一个操作来炉子 $$$3$$$,$$$A = [0, 1, 1, 3, 2, -2, 9]$$$。
- Pak Chanek 执行了一项操作来加热 $$$6$$$,$$$A = [0, 1, 1, 3, 0, 2, 7]$$$。
没有其他操作序列使得所需的操作数少于 $$$4$$$。