Archeologists#10880
Your treasure hunter team has just discovered a giant archeological site, full of precious metals and valuable antiquities. The site is composed of digging spots on a line.
The initial plans suggest that each of the digging spots has a net profit associated with it. The -th spot's associated profit is p_i. More specifically, this means that your team would gain p_i dollars for each meter dug in the -th spot. Note that p_i may also be negative, which means that the running cost of the excavating machinery surpasses the actual gain from digging in the -th spot.
Naturally, you would want to dig as much as possible in the most profitable spots. However, in order not to cause landslides, you are not allowed to have slopes that are too steep. More precisely, for any two adjacent spots, the difference between the digging depths at these spots cannot be more than meter. In particular, spots and can be dug only at most meter deep.
What is the largest net profit that you can obtain, under these conditions?
For instance, a valid digging plan that turns out to be optimal in the case of the first example input is illustrated below. The net profit of such plan is .
The first line will contain a positive integer n~(1 \le n \le 250 000).
The second line will contain integers p_i~(-10^6 \le p_i \le 10^6).
Output exactly one integer, the largest profit that you can obtain.
Example 1
Example 2
Example 3