CF1868F.LIS?

Entering senior high school life, Tom is attracted by LIS problems, not only the Longest Increasing Subsequence problem, but also the Largest Interval Sum problem. Now he gets a really interesting problem from his friend Daniel. However, it seems too hard for him to solve it, so he asks you for help.

Given an array $a$ consisting of $n$ integers.

In one operation, you do the following:

• Select an interval $[l,r]$ ($1\le l\le r\le n$), such that the sum of the interval is the largest among all intervals in the array $a$. More formally, $\displaystyle\sum_{i=l}^r a_i=\max_{1\le l'\le r'\le n}\sum_{i=l'}^{r'} a_i$.
• Then subtract $1$ from all elements $a_l,a_{l+1},\ldots,a_r$.

Find the minimum number of operations you need to perform to make $a_i \lt 0$ for every $1\le i\le n$.

进入高中生活后，汤姆被最长上升子序列（LIS）类问题所吸引，不仅包括“最长上升子序列”问题，还包括“最大区间和”问题。现在，他的朋友丹尼尔给了他一道非常有趣的问题。然而，这个问题对他而言似乎过于困难，因此他向你求助。

给定一个由 $n$ 个整数组成的数组 $a$。

每次操作中，你需要执行以下步骤：

• 选择一个区间 $[l,r]$（其中 $1\le l\le r\le n$），使得该区间的元素和是数组 $a$ 中所有区间中最大的。更准确地说，需满足
  $\displaystyle\sum_{i=l}^r a_i=\max_{1\le l'\le r'\le n}\sum_{i=l'}^{r'} a_i$。
• 然后将区间内所有元素 $a_l,a_{l+1},\ldots,a_r$ 各减去 $1$。

求使对所有 $1\le i\le n$ 均有 $a_i \lt 0$ 所需的最少操作次数。

The first line of input contains a single integer $n$ ($1 \le n \le 5 \cdot 10^5$) — the length of the array $a$.

The second line contains $n$ integers $a_1,a_2,\ldots,a_n$ ($-10^6\le a_i\le 10^6$) — the elements of the array $a$.

输入的第一行包含一个整数 $n$（$1 \le n \le 5 \cdot 10^5$）—— 数组 $a$ 的长度。

第二行包含 $n$ 个整数 $a_1,a_2,\ldots,a_n$（$-10^6\le a_i\le 10^6$）—— 数组 $a$ 的元素。

Print a single integer — the minimum number of operations.

输出一个整数——最小操作次数。

In the first example, you can do operations on intervals $[1,5],[1,5],[2,5],[3,5],[4,5],[5,5]$ in such order. You may also do operations on intervals $[1,5],[2,5],[3,5],[4,5],[5,5],[1,5]$ in such order.

In the second example, it's already satisfied that $a_i \lt 0$ for every $1\le i\le n$. So you do not need to perform any operations.

在第一个例子中，你可以按如下顺序对区间 $[1,5],[1,5],[2,5],[3,5],[4,5],[5,5]$ 执行操作。你也可以按如下顺序对区间 $[1,5],[2,5],[3,5],[4,5],[5,5],[1,5]$ 执行操作。

在第二个例子中，已满足对每个 $1\le i\le n$ 都有 $a_i \lt 0$，因此无需执行任何操作。