SP2185 MUSIC - Musical Optimization

贝茜是一头会写音乐旋律的奶牛。我们将一段音乐旋律表示为一个包含 $N$（$1 \le N \le 100,000$）个音符的序列，音符按顺序编号为 $1$ 到 $N$。每个音符 $i$ 用一个整数 $A_i$ 表示，其中 $-10,000 \le A_i \le 10,000$。 在贝茜的视角中，当一段旋律的每个连续子串的音符之和都严格大于零时，才可以称这段旋律为「完美」。 现在，贝茜希望将一段给定的旋律变得完美，并且她想尽量少地改变旋律。 为此，她会反复选择一个连续子串 $[x, y]$（$1 < x \le y < N$），如果该子串的和 $S$ 为负数，她将 $S$ 加到 $A_{x-1}$ 和 $A_{y+1}$ 上，同时从 $A_x$ 和 $A_y$ 中减去 $S$。（如果 $x = y$，可能会对同一个音符重复操作。） 给定一段音乐旋律，计算最少需要多少步操作可以让旋律变得完美。如果无法实现，则输出 -1。

* 第 1 行：一个整数 $N$。 * 第 2 到 $N+1$ 行：每行包含一个整数 $A_i$，表示音符的值。

* 仅一行：输出一个整数，表示将音乐旋律变得完美所需的最小步骤数。如果无法实现，输出 -1。

$1 \le N \le 100,000$ $-10,000 \le A_i \le 10,000$ **本翻译由 AI 自动生成**