Misery Business

Points: 1

Time limit: 1.0s

Memory limit: 256M

Author:

oree

Problem type

Allowed languages

C, C++, Java, Python

After long campaigns of layoffs and agentic workflow improvement, AllUni Co's workforce has reached peak performance. Now that there is nothing more to fix internally, Patrick, an AllUni director, shifts his focus to more external issues. Employees have been grumbling that the single escalator that leads into the office is a bottleneck. It can only fit $1$ ~1~ or $2$ ~2~ people abreast, and at 9am, there are sometimes thousands of people trying to enter the AllUni office! Patrick is tasked with redesigning these escalators to avoid bottlenecks and overtakes, and he needs your help!

The researchers have modelled a worst-case rush hour for you to design your system after. There are $n$ ~n~ people, each with a given walking speed. There are also multiple escalator lanes. Each lane must maintain a non-increasing order of speeds to avoid collisions and overtakes.

When a new person arrives:

They must join an existing lane where their speed is less than or equal to the last person's speed in that lane, so they don't have to overtake or collide.
Among all such lanes, they choose the one whose last person has the smallest possible speed greater than or equal to theirs (to minimise gaps and keep things efficient).
If no such lane exists, a new lane is created.

Your job is, given this model day with the speeds of each person, calculate the minimum number of escalator lanes needed, so Patrick can implement a more efficient escalator system and remove wasted commute time from the AllUni Co workers' days.

Input

The first line contains a single integer $n$ ~n~ $(1 \leq n \leq 5\times 10^5)$ ~(1 \leq n \leq 5\times 10^5)~, the number of people entering the office at once on this model workday start.

The next line contains $n$ ~n~ space-separated integers $s_1, \dots, s_n$ ~s_1, \dots, s_n~ $(1 \leq s_i \leq 10^9)$ ~(1 \leq s_i \leq 10^9)~, the walking speeds of each of the $n$ ~n~ people entering AllUni Co.

Output

Output the minimum number of lanes required to allow all people to enter the office efficiently as outlined above. The people enter the escalators in the order in which they appear in the input.

Example

Input 1

5
5 2 4 3 1

Output 1

When the first person enters, there are no lanes, so a new lane must be created for them.
When the second person enters, they are slower than the first person, so they can slot behind them in the existing lane.
When the third person enters, they are faster than the previous person ( $4 > 2$ ~4 > 2~), so a second lane must be created.
When the fourth person enters, they will slot behind the person of speed $4$ ~4~.
Finally, the fifth person enters. Currently, one lane has a last person with speed of $2$ ~2~, and the other has a last person of speed $3$ ~3~. Since $1$ ~1~ is less than both these, the person will enter the first existing lane (since $2 < 3$ ~2 < 3~).

Thus, only $2$ ~2~ lanes need exist to accommodate these workers entering.

Input 2

5
1 2 3 4 5

Output 2

Each person must have their own lane.

Input 3

6
3 1 2 1 2 3

Output 3

Comments

-1

Cookies commented on May 23, 2026, 5:25 a.m.

n = int(input()) s = list(map(int,input().split())) lanes = []

def insert_index(array,target): low, high = 0, len(array)-1 while low <= high: mid = low + (high - low) // 2 if array[mid] < target: high = mid -1 elif array[mid] > target: low = mid + 1 else: return mid return low -1

print("insert_index",insert_index([5,3],99))

for i in range(n): element = s[i] target_index = insert_index(lanes,element) if target_index == -1: lanes.insert(0,element) continue lanes[target_index] = element

print(len(lanes))