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 little arrows as possible.

입력

• The first line of input contains the integer N (1 ≤ N ≤ 1 000 000).
• The second line of input contains an array of N integers Hi. Each integer Hi (1 ≤ Hi ≤ 1 000 000) is the height at which the i th balloon floats, respectively from left to right.

출력

입출력 예

input

5
2 1 5 4 3

output

2

input

5
1 2 3 4 5

output

5

input

5
4 5 2 1 4

output
3

Clarification of the first example: Our hero shoots the arrow at height 5 - which destroys [5, 4, 3],
and shoots an arrow at height 2 - which destroys [2, 1]. 

출처:coci/2015-2016/contest1 3/6