from typing import Optional


class Node:
    def __init__(self, key, value):
        self.key = key
        self.value = value
        self.next: Optional[Node] = None
        self.prev: Optional[Node] = None

class LRUCache:

    def __init__(self, capacity: int):
        self.capacity = capacity
        self.map = {}
        self.head = Node(-1, -1)
        self.tail = Node(-1, -1)
        self.head.next, self.tail.prev = self.tail, self.head

    def get(self, key: int) -> int:
        if not key in self.map:
            return -1
        node = self.map[key]
        self._deleteAndAdd(node)
        return node.value
        
    def put(self, key: int, value: int) -> None:
        newNode = Node(key, value)
        if key in self.map:
            self._delete(self.map[key])
        else:
            if len(self.map.keys())+1 > self.capacity:
                del self.map[self.head.next.key]
                self._delete(self.head.next)
        self._add(newNode)
        self.map[key] = newNode

    def _deleteAndAdd(self, node):
        self._delete(node)
        self._add(node)

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

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