import java.util.*;

public class LruCache<K,V> implements Map<K,V> {
    private final Map<K,V> map;
    private final PriorityQueue<K> priorityQueue;
    private final Map<K,Integer> counts;
    private final int maxSize;

    public LruCache(int maxSize) {
        this.map = new HashMap<>(maxSize);
        this.maxSize = maxSize;
        this.counts = new HashMap<>(maxSize);
        this.priorityQueue = new PriorityQueue<>(this::compareToKeysByCount);
    }
    @Override
    public int size() {
        return map.size();
    }

    @Override
    public boolean isEmpty() {
        return map.isEmpty();
    }

    @Override
    public boolean containsKey(Object key) {
        return map.containsKey(key);
    }

    @Override
    public boolean containsValue(Object value) {
        return map.containsValue(value);
    }

    @Override
    public V get(Object key) {
        counts.put((K) key, counts.getOrDefault(key, 0) + 1);
        priorityQueue.remove(key);
        priorityQueue.add((K) key);
        return map.get(key);
    }

    @Override
    public V put(K key, V value) {
        V oldValue = null;
        if (!map.containsKey(key) && map.size() >= maxSize) {
            var removedKey = priorityQueue.remove();
            counts.remove(removedKey);
            oldValue = map.get(removedKey);
            map.remove(removedKey);
            //System.out.println("Removing from LRUCache : " + removedKey);
        }
        counts.put(key, 0);
        V oldValue2 = map.put(key, value);
        priorityQueue.add(key);
        return oldValue != null ? oldValue : oldValue2;
    }

    @Override
    public V remove(Object key) {
        counts.remove(key);
        priorityQueue.remove(key);
        return map.remove(key);
    }

    @Override
    public void putAll(Map<? extends K, ? extends V> m) {
        for (Map.Entry<? extends K, ? extends V> entry : m.entrySet()) {
            put(entry.getKey(), entry.getValue());
        }
    }

    @Override
    public void clear() {
        map.clear();
        priorityQueue.clear();
        counts.clear();
    }

    @Override
    public Set<K> keySet() {
        return map.keySet();
    }

    @Override
    public Collection<V> values() {
        return map.values();
    }

    @Override
    public Set<Entry<K, V>> entrySet() {
        return map.entrySet();
    }

    private int compareToKeysByCount(Object o1, Object o2) {
        return counts.getOrDefault(o1, 0) - counts.getOrDefault(o2, 0);
    }
}
