write a go solution for Description:
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<=l<=r<=n), such that the sum of the interval is the largest among all intervals in the array a. More formally, displaystylesum_i=l^ra_i=max_1<=l'<=r'<=nsum_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<=i<=n.

Input Format:
The first line of input contains a single integer n (1<=n<=5*10^5) — the length of the array a.

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

Output Format:
Print a single integer — the minimum number of operations.

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<=i<=n. So you do not need to perform any operations.. Output only the code with no comments, explanation, or additional text.