Por Dâmi Henrique, Inatel Brazil
Smider Pan is a hero and his hobby is to jump every night between the buildings of the populous city of Yew Nork. What people don't know is that Smider doesn't randomly jump between the buildings, his jumps follow a small pattern defined below:
- Smider starts somewhere on the ground where the height is considered to be 0.
- Initially he jumps only to the top of buildings that are higher than his current height.
- At a given moment he begins to jump only to buildings of lower heights than his current height until he reaches back the ground.
- As soon as he reaches the ground he takes off his outfit and goes home to get a rest.
At the left picture it's possible to see two possible sequences of jumps (green and blue) with 5 jumps each.
At the right picture there is a non-optimal jump sequence (yellow) and an invalid jump sequence (red).
Given the heights of N Yew Nork city buildings and knowing that Smider jumps only from left to right, your task is to calculate the largest amount of jumps he can perform respecting his previously defined jump pattern.
The first line contains an integer N (1 ≤ N ≤ 103) representing the number of Yew Nork buildings.
The second line will have N integers Hi (1 ≤ Hi ≤ 106), those being the heights of the buildings.
Print a single integer representing the greatest possible amount of jumps that Smider Pan will be able to perform.
|Input Sample||Output Sample|