class LRUCache:
    class _Node:
        __slots__ = ("key", "value", "prev", "next")

        def __init__(self, key=None, value=None):
            self.key = key
            self.value = value
            self.prev = None
            self.next = None

    def __init__(self, capacity):
        self.capacity = capacity
        self._map = {}
        # Sentinel head (most recently used side) and tail (LRU side).
        self._head = self._Node()
        self._tail = self._Node()
        self._head.next = self._tail
        self._tail.prev = self._head

    def _remove(self, node):
        node.prev.next = node.next
        node.next.prev = node.prev

    def _insert_front(self, node):
        node.prev = self._head
        node.next = self._head.next
        self._head.next.prev = node
        self._head.next = node

    def get(self, key):
        node = self._map.get(key)
        if node is None:
            return -1
        self._remove(node)
        self._insert_front(node)
        return node.value

    def put(self, key, value):
        if self.capacity <= 0:
            return
        node = self._map.get(key)
        if node is not None:
            node.value = value
            self._remove(node)
            self._insert_front(node)
            return
        node = self._Node(key, value)
        self._map[key] = node
        self._insert_front(node)
        if len(self._map) > self.capacity:
            lru = self._tail.prev
            self._remove(lru)
            del self._map[lru.key]