from collections import OrderedDict


class LRUCache:
    def __init__(self, capacity: int):
        self.cache = OrderedDict()
        self.current_capacity = 0
        self.max_capacity = capacity

    def get(self, key: int) -> int:
        if key in self.cache:
            self.cache.move_to_end(key)
        return self.cache.get(key, -1)

    def put(self, key: int, value: int) -> None:
        if key in self.cache:
            self.cache[key] = value
            self.cache.move_to_end(key)
        else:
            if self.current_capacity == self.max_capacity:
                self.cache.popitem(last=False)
            self.current_capacity = min(self.current_capacity+1, self.max_capacity)
            self.cache[key] = value


if __name__ == "__main__":
    cache = LRUCache(2)
    cache.put(1, 1)
    cache.put(2, 2)
    assert cache.get(1) == 1
    cache.put(3, 3)
    assert cache.get(2) == -1
    cache.put(4, 4)
    assert cache.get(1) == -1
    assert cache.get(3) == 3
    assert cache.get(4) == 4

    lru = LRUCache(10)
    lru.put(10, 13)
    lru.put(3, 17)
    lru.put(6, 11)
    lru.put(10, 5)
    lru.put(9, 10)
    lru.get(13)
    lru.put(2, 19)
    lru.get(2)
    lru.get(3)
    lru.put(5, 25)
    lru.get(8)
    lru.put(9, 22)
    lru.put(5, 5)
    lru.put(1, 30)
    lru.get(11)
    lru.put(9, 12)
    lru.get(7)
    lru.get(5)
    lru.get(8)
    lru.get(9)
    lru.put(4, 30)
    lru.put(9, 3)
    lru.get(9)
    lru.get(10)
    lru.get(10)
    lru.put(6, 14)
    lru.put(3, 1)
    lru.get(3)
    lru.put(10, 11)
    lru.get(8)
    lru.put(2, 14)
    lru.get(1)
    lru.get(5)
    lru.get(4)
    lru.put(11, 4)
    lru.put(12, 24)
    lru.put(5, 18)
    lru.get(13)
    lru.put(7, 23)
    lru.get(8)
    lru.get(12)
    lru.put(3, 27)
    lru.put(2, 12)
    lru.get(5)
    lru.put(2, 9)
    lru.put(13, 4)
    lru.put(8, 18)
    lru.put(1, 7)
    lru.get(6)
    lru.put(9, 29)
    lru.put(8, 21)
    lru.get(5)
    lru.put(6, 30)
    lru.put(1, 12)
    lru.get(10)
    lru.put(4, 15)
    lru.put(7, 22)
    lru.put(11, 26)
    lru.put(8, 17)
    lru.put(9, 29)
    lru.get(5)
    lru.put(3, 4)
    lru.put(11, 30)
    lru.get(12)
    lru.put(4, 29)
    lru.get(3)
    lru.get(9)
    lru.get(6)
    lru.put(3, 4)
    lru.get(1)
    lru.get(10)
    lru.put(3, 29)
    lru.put(10, 28)
    lru.put(1, 20)
    lru.put(11, 13)
    lru.get(3)
    lru.put(3, 12)
    lru.put(3, 8)
    lru.put(10, 9)
    lru.put(3, 26)
    lru.get(8)
    lru.get(7)
    lru.get(5)
    lru.put(13, 17)
    lru.put(2, 27)
    lru.put(11, 15)
    lru.get(12)
    lru.put(9, 19)
    lru.put(2, 15)
    lru.put(3, 16)
    lru.get(1)
    lru.put(12, 17)
    lru.put(9, 1)
    lru.put(6, 19)
    lru.get(4)
    lru.get(5)
    lru.get(5)
    lru.put(8, 1)
    lru.put(11, 7)
    lru.put(5, 2)
    lru.put(9, 28)
    lru.get(1)
    lru.put(2, 2)
    lru.put(7, 4)
    lru.put(4, 22)
    lru.put(7, 24)
    lru.put(9, 26)
    lru.put(13, 28)
    lru.put(11, 26)
