Codingpur's mayor decided to take a day off and play video game with his children. They started playing a video game named "Pipe-run". In this game, pipes of different sizes are placed in a row. At the start of the game, a ball is placed in a random pipe, and the size of the ball is equal to the size of the pipe. The ball can be moved left or right. It is not possible for a ball to pass through a pipe if the ball is of larger size than the pipe. If the ball needs to pass through a pipe of smaller size then he needs to use a spell that will make the size of the ball same as that of the pipe. The player will be given the size of all the pipes and the way they are placed. The player needs to get the ball out of the entire pipe system using minimum spells. The mayor knew that his children were best at this game, so they will always use minimum spells to get out of the pipe system. However, the mayor wanted to know the maximum amount of spells required by his children to get out of the given pipe system, that is the spells required considering the worst case.
Note:- A ball can easily pass through a pipe of same size. Also, it is not necessary that if the ball is moving left it needs to constantly move left. The ball can be made to change direction anywhere infinitely many times, according to the need of the player.
NOTE: Please use fast i/o for solving this problem.
See the sample case for better understanding.
Input format:
First line contains an integer n denoting the number of pipes.
Next line contains n space separated integers(s1, s2, .....sn). Here, si denotes the size of ith pipe from left.
Output format:
Print the number of spells required to get the ball out of the given pipe system, considering worst case.
Constraints:
1 <= n <= 10000000(1e7)
1 <= si <= 1000000000(1e9)
If the ball is placed in the pipe of size 5 i.e. in the pipe at index 2, then the ball can move left, use spell at index 1 pipe, that is of size 4 and then move left to get out pf the pipe system. Hence, spells required will be 1.
If the ball is placed in pipe of size 7 i.e. in the pipes at either index 3 or 4, then the ball can move right, use spell at index 5 pipe, that is of size 3 and then move left and get out of the pipe system.(As the ball becomes of size 3, he can easily pass through all the pipes in the right). Hence, spells required will 1.
If the ball is placed in any other pipes then the spells required will be 0.
Hence, in worst case that is considering that the ball is placed in either pipe 2, 3 or 5, the spells required will be 1. Hence, answer is 1.
