Problem Description
A fire has broken out in a large tower with N floors, and there is a person stuck at each floor trying to get out. Feeling his internal sense of justice raging, Rar the Cat took to his helicopter and flew
up to the top of the tower to attempt to save the people in the tower. When he got to the top of the tower, he found an empty lift shaft that was blown out by the fire. Peering into the lift shaft, he found that everyone
was still busy playing Flappy Bird!
Wait what... a high score of 145? How could this be? How could anyone beat the mighty Rar the Cat? Fury raged inside Rar the Cat. Conflicted between the urge for revenge and the rivalry between his Flappy Bird
foes, he comes out with a new plan. To save the people in the building, Rar the Cat will throw lift cars down the lift shaft to pick the people up. Since there is no electricity, the lift cars can only go downwards from
floor N to the ground floor, where the people are supposed to get to. To execute his brilliant revenge plan, a lift car can only pick up a person at a certain floor if all the people currently in the lift
car has a Flappy Bird high score higher than the person currently entering it.
Given a list of the Flappy Bird high scores of each of the people on each floor, find out the minimum number of lift cars Rar the Cat has to throw down to get everyone down to the ground floor.
Input
The first line of input will contain one integer,
N.
The second line of input will contain
N integers, with the
ith integer representing the Flappy Bird high score of the person on
floor
i.
Output
Your output should contain one integer, the minimum number of lift cars Rar the Cat has to throw down to get everyone down to the ground floor.
Limits
All Flappy Bird high scores
will be less than 2
31-1.
Subtask 1 (14%): 1 ≤ N ≤ 10. In addition, all Flappy Bird high scores will be less than or equal to 10.
Subtask 2 (28%): 1 ≤ N ≤ 1000.
Subtask 3 (58%): 1 ≤ N ≤
1000000.
Subtask 4 (0%): As per sample testcases.
Sample Input 1
5
1 2 3 3 5
Sample Output 1
2
Sample Input 2
5
5 4 2 5 1
Sample Output 2
4