A customer service queue is a singly linked list of ticket priorities, in arrival order (front to back). Management wants the remaining queue, after evicting some tickets WITHOUT reordering the rest, to be STRICTLY INCREASING in priority from front to back. Find the MINIMUM number of tickets that must be evicted to achieve this, and print that minimum count.
Line 1: an integer n — the number of tickets.
Line 2: n space-separated integers — the ticket priorities, in arrival order.
A single integer: the minimum number of tickets that must be evicted so the remaining priorities are strictly increasing front to back.
Example 1
Input
6 5 1 6 2 7 3
Expected
3
Explanation
The longest strictly increasing subsequence, e.g. 1,2,7, has length 3, so 6 - 3 = 3 tickets must be evicted.
Example 2
Input
4 1 2 3 4
Expected
0
Explanation
The queue is already strictly increasing, so 0 evictions are needed.
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →