ICPC Judge Anton got the hunter bow and the arrows as a birthday gift.
After the last onsite ICPC event, there are spare balloons in the room. The balloons are lined up such that -th balloon is placed in the point with coordinates (i,0,h_i), where h_i is a positive integer.
Anton decided to use those balloons to train his hunting skills.
Anton is located at (0,0,0), and he may shoot at the any integer height, i.e. from point (0,0,h_j). When he shoots an arrow, it starts to move from (0,0,h_j) horizontally by the direction of increasing the first coordinate. That is, it will be in (1,0,h_j) first, (2,0,h_j) later, and so on.
When an arrow touches a balloon, the balloon bursts, and the height of the arrow decreases by one. That is, if the coordinates were (d,0,h_j) then they would be (d,0,h_j-1). Then arrow continues moving horizontally at the new height. If the height decreases to zero, the arrow lands on the floor.
Note that the second coordinate will always be . It is given in order to make it easier to understand the statement.
Find out the minimum number of arrows needed to burst all the balloons.
The first line contains the only integer (1 \le N \le 10^6).
The second line contains integers h_i (1 \le h_i \le 10^6) — the height of the -th balloon.
Print out the minimum number of arrows needed to burst all the balloons.
Example 1