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.
Input format
Line 1: an integer n — the number of tickets.
Line 2: n space-separated integers — the ticket priorities, in arrival order.
Output format
A single integer: the minimum number of tickets that must be evicted so the remaining priorities are strictly increasing front to back.
Constraints
- 1 ≤ n ≤ 100000
- -1000000000 ≤ priority ≤ 1000000000