CF1868F LIS?

进入高中生活后，Tom 被 LIS 问题所吸引，不仅仅是最长上升子序列问题，还有最大区间和问题。现在他从朋友 Daniel 那里得到了一个非常有趣的问题。然而，这个问题对他来说似乎太难了，于是他向你寻求帮助。 给定一个由 $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 < 0$，所需的最少操作次数。

输入的第一行包含一个整数 $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$ 的元素。

输出一个整数，表示所需的最少操作次数。

在第一个样例中，你可以依次对区间 $[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 < 0$，因此你不需要进行任何操作。 由 ChatGPT 4.1 翻译