CF1725L.Lemper Cooking Competition

Pak Chanek is participating in a lemper cooking competition. In the competition, Pak Chanek has to cook lempers with $N$ stoves that are arranged sequentially from stove $1$ to stove $N$. Initially, stove $i$ has a temperature of $A_i$ degrees. A stove can have a negative temperature.

Pak Chanek realises that, in order for his lempers to be cooked, he needs to keep the temperature of each stove at a non-negative value. To make it happen, Pak Chanek can do zero or more operations. In one operation, Pak Chanek chooses one stove $i$ with $2 \leq i \leq N-1$, then:

1. changes the temperature of stove $i-1$ into $A_{i-1} := A_{i-1} + A_{i}$,
2. changes the temperature of stove $i+1$ into $A_{i+1} := A_{i+1} + A_{i}$, and
3. changes the temperature of stove $i$ into $A_i := -A_i$.

Pak Chanek wants to know the minimum number of operations he needs to do such that the temperatures of all stoves are at non-negative values. Help Pak Chanek by telling him the minimum number of operations needed or by reporting if it is not possible to do.

Pak Chanek 正在参加一场粽子（lemper）烹饪比赛。在该比赛中，Pak Chanek 需要使用 $N$ 台依次排列的炉灶来烹制粽子，编号从炉灶 $1$ 到炉灶 $N$。初始时，炉灶 $i$ 的温度为 $A_i$ 摄氏度。炉灶的温度可以为负数。

Pak Chanek 意识到，为了让他的粽子成功烹熟，他必须使每台炉灶的温度均保持为非负值。为此，Pak Chanek 可以执行零次或多次操作。每次操作中，Pak Chanek 选择一台满足 $2 \leq i \leq N-1$ 的炉灶 $i$，然后：

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，告诉他所需的最少操作次数；若无法实现，则报告“不可能”。

The first line contains a single integer $N$ ($1 \le N \le 10^5$) — the number of stoves.

The second line contains $N$ integers $A_1, A_2, \ldots, A_N$ ($-10^9 \leq A_i \leq 10^9$) — the initial temperatures of the stoves.

第一行包含一个整数 $N$（$1 \le N \le 10^5$）—— 炉子的数量。

第二行包含 $N$ 个整数 $A_1, A_2, \ldots, A_N$（$-10^9 \leq A_i \leq 10^9$）—— 各炉子的初始温度。

Output an integer representing the minimum number of operations needed to make the temperatures of all stoves at non-negative values or output $-1$ if it is not possible.

输出一个整数，表示使所有炉灶温度均变为非负值所需的最少操作次数；若无法实现，则输出 $-1$。

For the first example, a sequence of operations that can be done is as follows:

• Pak Chanek does an operation to stove $3$, $A = [2, -2, 1, 4, 2, -2, 9]$.
• Pak Chanek does an operation to stove $2$, $A = [0, 2, -1, 4, 2, -2, 9]$.
• Pak Chanek does an operation to stove $3$, $A = [0, 1, 1, 3, 2, -2, 9]$.
• Pak Chanek does an operation to stove $6$, $A = [0, 1, 1, 3, 0, 2, 7]$.

There is no other sequence of operations such that the number of operations needed is fewer than $4$.

对于第一个样例，一种可行的操作序列如下：

• 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$ 的其他操作序列。