进入高中生活,Tom被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<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 2 3 4 5
输出 #1
6
输入 #2
6 -1 -5 -4 -1 -4 -7
输出 #2
0
输入 #3
11 0 1000000 1 -50000 2 998353 3 -100007 4 200943 0
输出 #3
1936973
注意
在第一个示例中,您可以按以下顺序对区间 $$$[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$$$。所以你不需要执行任何操作。