Problem E
Baloni
There are $N$ balloons floating in the air in a large room, lined up from left to right. Young Perica likes to play with arrows and practice his hunting abilities. He shoots an arrow from the left to the right side of the room from an arbitrary height he chooses. The arrow moves from left to right, at a chosen height $H$ until it finds a balloon. The moment when an arrow touches a balloon, the balloon pops and disappears and the arrow continues its way from left to right at a height decreased by $1$. Therefore, if the arrow was moving at height $H$, after popping the balloon it travels on height $H-1$.
Our hero’s goal is to pop all the balloons using as few arrows as possible.
Input
The first line of input contains the integer $N$ ($1 \leq N \leq 1\ 000\ 000$). The second line of input contains an array of $N$ integers $H_ i$. Each integer $H_ i$ ($1 \leq H_ i \leq 1\ 000\ 000$) is the height at which the $i$-th balloon floats, respectively from left to right.
Output
The first and only line of output must contain the minimal number of times Pero needs to shoot an arrow so that all balloons are popped.
| Sample Input 1 | Sample Output 1 |
|---|---|
5 2 1 5 4 3 |
2 |
| Sample Input 2 | Sample Output 2 |
|---|---|
5 1 2 3 4 5 |
5 |
| Sample Input 3 | Sample Output 3 |
|---|---|
5 4 5 2 1 4 |
3 |