from structures import run_operations

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

class LRUCache:
    def __init__(self, capacity):
        self.capacity, self.nodes = capacity, {}
        self.head, self.tail = CacheNode(), CacheNode()
        self.head.next, self.tail.prev = self.tail, self.head

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

    def _append_recent(self, node):
        previous = self.tail.prev
        previous.next, node.prev = node, previous
        node.next, self.tail.prev = self.tail, node

    def get(self, key):
        if key not in self.nodes:
            return -1
        node = self.nodes[key]
        self._detach(node)
        self._append_recent(node)
        return node.value

    def put(self, key, value):
        if key in self.nodes:
            node = self.nodes[key]
            node.value = value
            self._detach(node)
        else:
            node = CacheNode(key, value)
            self.nodes[key] = node
        self._append_recent(node)
        if len(self.nodes) > self.capacity:
            oldest = self.head.next
            self._detach(oldest)
            del self.nodes[oldest.key]