410125: GYM103960 E Eliminating Ballons

An enormous number of balloons are floating about in the Convention Hall after the Awarding Ceremony of the ICPC Subregional Contest. The manager of the Convention Hall is angry, because he will host another event tomorrow and the balloons must be removed. Fortunately this year Carlinhos came prepared with his bow and arrows to pop the balloons.

Also, luckily, due to the air conditioning flow, the balloons are all in the same vertical plane (that is, a plane parallel to a wall), although in distinct heights and positions.

Carlinhos will shoot from the left side of the convention hall, at a chosen height, in the direction of the right side of the Convention Hall. Each arrow moves from left to right, at the height it was shot, in the same vertical plane of the balloons. When an arrow touches a balloon, the balloon pops and the arrow continues its movement to the right, at a height decreased by 1. In other words, if the arrow was at height $$$H$$$, after popping a balloon it continues at height $$$H - 1$$$.

Carlinhos wants to pop all balloons shooting as few arrows as possible. Can you help him?

The first line of input contains an integer $$$N$$$, the number of balloons ($$$1 \le N \le 5 \times 10^5$$$). Since all balloons are in the same vertical plane, lets define that the height of a ballon is given in relation to the $$$y$$$-axis and the position of a balloon is given in relation to the $$$x$$$-axis. Balloons are numbered from 1 to $$$N$$$. Balloon numbers indicate theis positions, from leftmost (balloon number 1) to rightmost (balloon number $$$N$$$), independent of their heights. The position of balloon number $$$i$$$ is different from the position of balloon number $$$i+1$$$, for all $$$i$$$. The second line contains $$$N$$$ integers $$$H_i$$$, where $$$H_i$$$ indicates the height of balloon number $$$i$$$ ($$$1 \le H_i \le 10^6$$$ for $$$1 \le i \le N$$$). Notice that several balloons may be at the same height, but there are no repeated (position, height) pairs.

Your program must output a single line, containing a single integer, the minimum number of arrows that Carlinhos needs to shoot to pop all balloons.

5
3 2 1 5 4

2

4
1 2 3 4

4

6
5 3 2 4 6 1

3

5
1 1 1 1 1

5