The Reading-Room Shelf

A library reading room has a shelf with room for capacity books. Readers ask for books one at a time, listed in requests by book number. If the book is on the shelf, the reader takes it and puts it back in the same place: nothing moves. If it is not, a librarian fetches it from the basement (a fetch) and puts it on the shelf. When the shelf is already full, the librarian first sends back the book that has been on the shelf the longest, counted from the moment it was last fetched; how often it was read since then does not matter.

The shelf starts empty. Return the number of fetches.

Examples

Input:  requests = [1, 2, 3, 1, 4, 1, 2], capacity = 3
Output: 6
Explanation: 1, 2 and 3 are fetched (3). 1 is on the shelf. 4 is fetched and 1, the oldest
arrival, goes back although it was just read (4). 1 is fetched and 2 goes back (5).
2 is fetched and 3 goes back (6).

Input:  requests = [5, 5, 5], capacity = 1
Output: 1

Constraints

• 0 <= len(requests) <= 10**5
• 1 <= capacity <= 10**5
• book numbers are integers in 0..10**9

Goals

• Simulate a fixed-size cache that evicts in arrival order
• Keep a set for membership and a queue for the eviction order
• See that a hit does not change the order under this rule