The great pharaoh of Flatland recently ascended the throne and took care of the issue of building a pyramid for himself.
Flatland — a two-dimensional country, it only has length and height. For the construction of the pyramid, a plot with a length of N standard blocks was allocated. Each single segment was surveyed by geologists, who found out the number of standard 1 by 1 blocks that can be laid in a column on this cell without the threat of subsidence.
A pyramid is a figure consisting of 1 by 1 blocks, such that each horizontal layer is a continuous segment. Under each block there must be a block of the previous layer or ground (in the lower layer). The number of blocks in each column must not exceed the carrying capacity of the cell on which this column is located.
The pharaoh wants his pyramid to consist of as many blocks as possible. Help him determine this number.
Input data format
The first line of the input contains an integer N (1 ≤ N ≤ 300000) — section length,
allocated for the construction of the pyramid.
The second line contains N integers Wi (0 ≤ Wi ≤ 10
9) — lifting capacity of segments
single length.
Output data format
Print the maximum number of blocks a pyramid can be built from.
Examples
| # |
Input |
Output |
| 1 |
6
7 0 1 3 2 3
| 8 |