How Much Memory Does the Map Server Need?

A map server keeps recently drawn map tiles in memory. It can hold k tiles; a request for a tile that is not in memory is a miss: the tile is drawn and stored, and if memory is full one stored tile is thrown out first. Memory starts empty. Two eviction rules are on the table:

• recent: throw out the tile whose last request is the oldest (a request for a stored tile counts as a use);
• planned: the day's requests are known in advance, so throw out the tile whose next request is furthest in the future; tiles never requested again count as furthest of all, and any of them may be chosen.

The operators accept at most max_misses misses for the day. Return a tuple (recent_k, planned_k): for each rule, the smallest memory size k >= 1 for which the rule makes at most max_misses misses on requests. If no memory size is enough, return (-1, -1).

Examples

Input:  requests = [1, 2, 3, 1, 4, 1, 2, 5, 1, 2, 3, 4], max_misses = 7
Output: (4, 3)
Explanation: recent makes 8 misses with k = 3 and 7 with k = 4. planned makes 9 misses
with k = 2 and 7 with k = 3.

Input:  requests = [1, 2, 3, 1, 4, 1, 2, 5, 1, 2, 3, 4], max_misses = 6
Output: (5, 4)

Input:  requests = [1, 2, 3, 1, 4, 1, 2, 5, 1, 2, 3, 4], max_misses = 4
Output: (-1, -1)
Explanation: five different tiles are requested, and each one misses at least once.

Constraints

• 0 <= len(requests) <= 2 * 10**4; tile numbers are integers in 0..10**9
• 0 <= max_misses <= 10**5
• up to 10**4 different tiles; trying every memory size one after another is too slow

Goals

• Simulate least-recently-used and furthest-next-use eviction efficiently
• Recognise that both rules never miss more with a bigger cache
• Binary search over the cache size instead of trying every size
• Measure how much memory not knowing the future costs