eolymp
bolt
Try our new interface for solving problems
Problems

Archeologists

Archeologists

Time limit 1 second
Memory limit 128 MiB

Your treasure hunter team has just discovered a giant archeological site, full of precious metals and valuable antiquities. The site is composed of n digging spots on a line.

The initial plans suggest that each of the n digging spots has a net profit associated with it. The i-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 i-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 i-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 depth at these spots cannot differ by more than 1 meter. In particular, spots 1 and n can be dug only at most 1 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 8.

#### Input The first line will contain a positive integer n~(1 \le n \le 250 000).

The second line will contain n integers p_i~(-10^6 \le p_i \le 10^6).

#### Output Output exactly one integer, the largest profit that you can obtain.

Examples

Input example #1
5
1 3 -4 2 1
Output example #1
8
Input example #2
4
1 1 -2 3
Output example #2
5
Input example #3
5
-1 -3 0 -5 -4
Output example #3
0
Source 2020 SEERC South Eastern European Regional Programming Contest, Vinnica & Bucharest, May 23, Problem A