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 pi. More specifically, this means that your team would gain pi dollars for each meter dug in the i-th spot. Note that pi 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 ≤ n ≤ 250 000).

The second line will contain n integers pi (-106 ≤ pi ≤ 106), separated by spaces.

Output

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