from collections import defaultdict, OrderedDict



class LFUCache:
    def __init__(self, capacity: int):
        self.capacity = capacity
        self.keyToVal = {}
        self.keyToFreq = {}
        # freq to ordering of keys (implemented as an OrderedDict of key to True which has fast remove and reinsert to back)
        self.freqToLRU = defaultdict(OrderedDict)
        # minFreq tracks smallest freq with non-empty list in freqToLRU
        self.minFreq = 0

    def _use(self, key: int) -> int:
        freq = self.keyToFreq[key]
        del self.freqToLRU[freq][key]  # Remove from `freq` list
        self.freqToLRU[freq + 1][key] = True  # Add to back of `freq + 1` list
        self.keyToFreq[key] = freq + 1
        if freq == self.minFreq and not self.freqToLRU[freq]:
            self.minFreq += 1

    def get(self, key: int) -> int:
        if key in self.keyToVal:
            self._use(key)
            return self.keyToVal[key]
        return -1

    def put(self, key: int, value: int) -> None:
        if self.capacity == 0:
            return
        if key in self.keyToVal:
            self._use(key)
            self.keyToVal[key] = value
        else:
            if len(self.keyToVal) == self.capacity:
                # Pop from front of `minFreq` list
                # Note: The list might become empty but we will be inserting a new key with freq 0 anyway
                evictKey, _ = self.freqToLRU[self.minFreq].popitem(last=False)
                del self.keyToFreq[evictKey]
                del self.keyToVal[evictKey]
            freq = 0
            self.keyToVal[key] = value
            self.keyToFreq[key] = freq
            self.freqToLRU[freq][key] = True
            self.minFreq = freq