Job Hunting

View as PDF

Submit solution

Points: 10
Time limit: 1.5s
Memory limit: 64M
PyPy 3 128M

Problem type

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 N positions that would open sometime in the future. For brevity, let's say that on the i-th day, a job with skill level A_i 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?


1\le A_i\le N

Subtask 1 [80%]

1\le N\le 2000

Subtask 2 [20%]

1\le N\le 2\times 10^5

Input Specification

The first line contains one integer: N.

The second line contains N integers, the i-th of which being A_i

Output Specification

One integer: the largest number of jobs Corey can try out

Sample Input

4 2 2 6 4 5

Sample Output


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.


There are no comments at the moment.