from collections import OrderedDict


class LRUCache:
    """Least-recently-used cache with O(1) get and put.

    Internally uses collections.OrderedDict, which maintains insertion order
    and provides O(1) move_to_end() and popitem(last=False) operations backed
    by a doubly-linked list in CPython, giving O(1) amortised complexity for
    all three required operations.
    """

    def __init__(self, capacity: int) -> None:
        self._capacity = capacity
        self._cache: OrderedDict = OrderedDict()

    def get(self, key: int) -> int:
        if key not in self._cache:
            return -1
        # Move to the end to mark as most recently used.
        self._cache.move_to_end(key)
        return self._cache[key]

    def put(self, key: int, value: int) -> None:
        if self._capacity == 0:
            return
        if key in self._cache:
            # Update value and refresh recency.
            self._cache.move_to_end(key)
            self._cache[key] = value
        else:
            # Evict LRU entry if at capacity (front of ordered dict).
            if len(self._cache) >= self._capacity:
                self._cache.popitem(last=False)
            self._cache[key] = value