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 at height ~H-1~.

Our hero's goal is to pop all the balloons using as few arrows as possible.

Input Specification

The first line of input contains the integer ~N~ ~(1 \le N \le 1\,000\,000)~.

The second line of input contains an array of ~N~ integers ~H_i~.

Each integer ~H_i~ ~(1 \le H_i \le 1\,000\,000)~ is the height at which the ~i^{th}~ balloon floats, respectively from left to right.

In test cases worth 40%, it will hold ~N \le 5\,000~.

Output Specification

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

5
2 1 5 4 3

Sample Output 1

2

Explanation for Sample Output 1

Our hero shoots the arrow at height ~5~ – which destroys ~[5, 4, 3]~, and shoots an arrow at height ~2~ – which destroys ~[2, 1]~.

Sample Input 2

5
1 2 3 4 5

Sample Output 2

5

Sample Input 3

5
4 5 2 1 4

Sample Output 3

3