310676: CF1868F. LIS?

F. LIS?time limit per test5 secondsmemory limit per test1024 megabytesinputstandard inputoutputstandard output

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<0$ for every $1\le i\le n$.

Input

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$.

Output

Print a single integer — the minimum number of operations.

ExamplesInput

5
1 2 3 4 5

Output

6

Input

6
-1 -5 -4 -1 -4 -7

Output

0

Input

11
0 1000000 1 -50000 2 998353 3 -100007 4 200943 0

Output

1936973

Note

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<0$ for every $1\le i\le n$. So you do not need to perform any operations.

题目大意：
汤姆上高中后对LIS问题（最长递增子序列问题）产生了兴趣，现在他从朋友丹尼尔那里得到了一个有趣的问题，但他觉得太难解决，所以向你求助。给定一个由n个整数组成的数组a。每次操作，你需要选择一个区间[l, r]，使得该区间的和是数组a中所有区间中最大的。然后从这个区间的所有元素中减去1。求需要进行的最小操作次数，使得对于每个1≤i≤n，都有a_i<0。

输入输出数据格式：
输入：
- 第一行包含一个整数n（1≤n≤5×10^5），表示数组a的长度。
- 第二行包含n个整数a_1, a_2, ..., a_n（-10^6≤a_i≤10^6），表示数组a的元素。

输出：
- 输出一个整数，表示需要进行的最小操作次数。

示例：
输入：
5
1 2 3 4 5
输出：
6

输入：
6
-1 -5 -4 -1 -4 -7
输出：
0

输入：
11
0 1000000 1 -50000 2 998353 3 -100007 4 200943 0
输出：
1936973题目大意： 汤姆上高中后对LIS问题（最长递增子序列问题）产生了兴趣，现在他从朋友丹尼尔那里得到了一个有趣的问题，但他觉得太难解决，所以向你求助。给定一个由n个整数组成的数组a。每次操作，你需要选择一个区间[l, r]，使得该区间的和是数组a中所有区间中最大的。然后从这个区间的所有元素中减去1。求需要进行的最小操作次数，使得对于每个1≤i≤n，都有a_i<0。 输入输出数据格式： 输入： - 第一行包含一个整数n（1≤n≤5×10^5），表示数组a的长度。 - 第二行包含n个整数a_1, a_2, ..., a_n（-10^6≤a_i≤10^6），表示数组a的元素。 输出： - 输出一个整数，表示需要进行的最小操作次数。 示例： 输入： 5 1 2 3 4 5 输出： 6 输入： 6 -1 -5 -4 -1 -4 -7 输出： 0 输入： 11 0 1000000 1 -50000 2 998353 3 -100007 4 200943 0 输出： 1936973