Reels in the Projection Booth

A film festival has published its whole screening schedule in advance: requests lists the reel numbers in the order they are projected. The projection booth holds at most capacity reels; the reels in start are already in the booth when the festival opens. Showing a reel that is in the booth costs nothing. Showing one that is not means a courier brings it from the archive, and if the booth is full a reel must first be returned to the archive to make room.

The festival wants as few courier trips as possible, so it always returns the reel in the booth whose next screening is furthest away. A reel that is never screened again counts as further away than any screening; if several reels are never screened again, the one with the smallest number is returned.

Return the list of returned reels, in the order they leave the booth.

Examples

Input:  requests = [1, 3, 2, 4, 1, 5, 2], capacity = 3, start = [7, 1, 2]
Output: [7, 3, 1]
Explanation: 3 needs room: 7 is never shown again, so it goes. 4 needs room: 3 is never shown
again (1 is next at position 4, 2 at 6). 5 needs room: 1 and 4 are both never shown again,
so the smaller number, 1, goes.

Input:  requests = [4, 1, 2, 3, 1], capacity = 2, start = []
Output: [4, 2]

Constraints

• 0 <= len(requests) <= 10**5
• 1 <= capacity <= 10**5; start holds at most capacity distinct reels
• reel numbers are integers in 0..10**9
• Target: O(n log n) time; comparing the next screening of every reel in the booth on each return is too slow when the booth is large

Goals

• Precompute, for every request, when the same item is needed next
• Find the item needed furthest in the future with a max-heap
• Skip stale heap entries instead of deleting them