Corey wants to climb the corporate ladder to greatness! To do so, he's going to jump between many jobs in order to increase his skills, but of course, he would prefer more jobs so he can escape commitment gather more experience! Due to his connections, he found positions that would open sometime in the future. For brevity, let's say that on the -th day, a job with skill level will open. Whenever Corey switches jobs from one to another, the second job must have a greater or equal skill level compared to his current job. Additionally, Corey is currently unemployed, so he will accept a job of any skill level as his first. Can you help him find how many different positions he can try, given that he must always switch to a position of higher or equal skill level?
Constraints
Subtask 1 [80%]
Subtask 2 [20%]
Input Specification
The first line contains one integer: .
The second line contains integers, the -th of which being
Output Specification
One integer: the largest number of jobs Corey can try out
Sample Input
6
4 2 2 6 4 5
Sample Output
4
Sample Explanation
It is best to take the second, third, fifth, and sixth jobs. Notice that their skill levels are 2 2 4 5
, so each job has a higher or equal skill level to the previous. This is also the maximum number of jobs Corey can take.
Comments