CF1725L Lemper Cooking Competition

Pak Chanek 正在参加一场 lemper 烹饪比赛。在比赛中，Pak Chanek 需要用 $N$ 个依次排列的炉灶（从第 $1$ 个到第 $N$ 个）来烹饪 lemper。最初，第 $i$ 个炉灶的温度为 $A_i$ 度。一个炉灶的温度可以为负数。 Pak Chanek 意识到，为了让他的 lemper 能够被烹饪好，他需要保证每个炉灶的温度都不为负。为此，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 想知道，他最少需要进行多少次操作，才能使所有炉灶的温度都不为负。如果无法做到，请输出 $-1$。

第一行包含一个整数 $N$（$1 \le N \le 10^5$），表示炉灶的数量。 第二行包含 $N$ 个整数 $A_1, A_2, \ldots, A_N$（$-10^9 \leq A_i \leq 10^9$），表示每个炉灶的初始温度。

输出一个整数，表示使所有炉灶温度都不为负所需的最小操作次数。如果无法做到，输出 $-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$ 次。 由 ChatGPT 4.1 翻译