LIS?
Contest: Codeforces Round 896 (Div. 1)
Difficulty rating: 3500
Tags: data structures, greedy, implementation

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 format:
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 format:
Print a single integer — the minimum number of operations.

Constraints:
Time limit: 5.0 s
Memory limit: 1024.0 MB

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.

Example input:
5
1 2 3 4 5

Example output:
6

Example input:
6
-1 -5 -4 -1 -4 -7

Example output:
0

Editorial:
Call an interval candidate good if and only if it has no prefixes or suffixes with sum $$$<0$$$.
For a candidate good interval $$$[l,r]$$$, if there is no $$$l'<l$$$ or $$$r'>r$$$ such that $$$[l',r]$$$, $$$[l,r']$$$ or $$$[l',r']$$$ is also a candidate good interval, we call it good interval.
It's easy to show that all intervals which satisfy the condition in the statement are candidate good intervals and at least one of them is a good interval.
Lemma 1. For two good intervals $$$[l_1,r_1]$$$ and $$$[l_2,r_2]$$$, they will never intersect. More formally:
• either $$$r_1<l_2$$$ or $$$r_2<l_1$$$;
• or $$$l_2 \le l_1\le r_1\le r_2$$$.
Greedy Algorithm. In each operation, we choose one good interval that satisfies the condition in the statement. This will give the minimum answer.
Following our process of the greedy algorithm, it's easy to see that the intervals on which we perform operations each time will form a tree structure. If we do the operation on one such interval, then one of the following happens:
• The interval remains good;
• The interval is no longer good, and we can split it into several good intervals.
In the first case, we can keep doing operations on this interval without thinking whether it will have the largest sum among all intervals since it remains good, and all good intervals must be split into shorter good intervals unless it has length $$$1$$$. In this case, we can simply do the operations until the only element falls $$$\le0$$$.
In the second case, let $$$(L_i,d)$$$ means that if all the elements in the interval decrease $$$d$$$ ($$$d$$$ is the smallest integer which meets with the following), then $$$s(L_i,r)>s(l,r)$$$.
That is, $$$$$$ d=\min_{l <l'\le r}\frac{s_r-s_{l'-1}}{r-l'}, $$$$$$ where $$$s_i=\sum_{j=1}^i a_i$$$. $$$(R_i,d)$$$ is defined similarly.
Have you noticed that it is very similar to the slope between points $$$(l'-1,s_{l'-1})$$$ and $$$(r,s_r)$$$ on a 2-D plane? So what we need to find is just the first point before $$$(r,s_r)$$$ (after $$$(l,s_l)$$$) in the convex hull for points $$$(l,s_l),(l+1,s_{l+1}),...,(r,r_s)$$$. To find it, we can use a segment tree to directly maintain the convex hull for certain intervals, each time we query $$$\mathcal{O}(\log n)$$$ intervals and do ternary search on the convex hull of each interval. This step will cost $$$\mathcal{O}(\log^2 n)$$$.
In each split, the number of good intervals increases $$$1$$$, so we do at most $$$n$$$ splits.
Overall time complexity is $$$\mathcal{O}(n\log^2 n)$$$.