People stand in a queue, front to back, and person i holds a ticket with the integer tickets[i]. The organiser wants the ticket numbers to be strictly increasing from the front of the queue to the back, and every ticket number must be an integer in the range lo..hi (inclusive).
To fix the queue the organiser may reissue tickets: a reissued ticket gets any integer the organiser likes. Tickets that are not reissued keep their original number, and a kept ticket must also lie in lo..hi. Nobody changes place in the queue.
Return the minimum number of tickets that must be reissued. If no assignment can satisfy the rules at all, return -1.
Examples
Input: tickets = [5, 1, 7, 12, 9, 15], lo = 1, hi = 20
Output: 2
Explanation: reissue the tickets 1 and 9, for example as 6 and 13,
giving [5, 6, 7, 12, 13, 15].
Input: tickets = [4, 4, 4], lo = 1, hi = 9
Output: 2
Explanation: keep one 4 and reissue the other two, e.g. [2, 3, 4] or [4, 5, 6].
Constraints
0 <= len(tickets) <= 10**5-10**9 <= tickets[i], lo, hi <= 10**9,lo <= hi- An empty queue needs no reissued tickets.
- Target complexity: O(n log n).
Goals
- Decide exactly which original values can be kept when the replacements must be integers
- Account for the limited range of ticket numbers at both ends of the queue
- Find a longest suitable subsequence in O(n log n)