from collections import OrderedDict

class LRUCache:

    def __init__(self, capacity: int):
        self.cache = OrderedDict()
        self.capacity = capacity

    def get(self, key: int) -> int:
        if key not in self.cache:
            return -1
        val = self.cache.pop(key)
        self.cache[key] = val
        return val

    def put(self, key: int, value: int) -> None:
        if key in self.cache:
            self.cache.pop(key)
            self.cache[key] = value
            return
        if len(self.cache) == self.capacity:
            self.cache.popitem(last=False)
        self.cache[key] = value


if __name__ == '__main__':
    s = LRUCache(2)
    s.put(2, 1)
    s.put(1, 1)
    s.put(2, 3)
    s.put(4, 1)
    print(s.get(1))
    print(s.get(2))
    s.put(4, 4)
