struct Node {
  int key;
  int value;
  Node(int key, int value) : key(key), value(value) {}
};

class LRUCache {
 public:
  LRUCache(int capacity) : capacity(capacity) {}

  int get(int key) {
    if (!keyToIterator.count(key))
      return -1;

    const auto& it = keyToIterator[key];
    // move it to the front
    cache.splice(begin(cache), cache, it);
    return it->value;
  }

  void put(int key, int value) {
    // no capacity issue, just update the value
    if (keyToIterator.count(key)) {
      const auto& it = keyToIterator[key];
      // move it to the front
      cache.splice(begin(cache), cache, it);
      it->value = value;
      return;
    }

    // check the capacity
    if (cache.size() == capacity) {
      const auto& lastNode = cache.back();
      // that's why we store `key` in `Node`
      keyToIterator.erase(lastNode.key);
      cache.pop_back();
    }

    cache.emplace_front(key, value);
    keyToIterator[key] = begin(cache);
  }

 private:
  const int capacity;
  list<Node> cache;
  unordered_map<int, list<Node>::iterator> keyToIterator;
};

class Node {
  public int key;
  public int value;

  public Node(int key, int value) {
    this.key = key;
    this.value = value;
  }
}

class LRUCache {
  public LRUCache(int capacity) {
    this.capacity = capacity;
  }

  public int get(int key) {
    if (!keyToNode.containsKey(key))
      return -1;

    Node node = keyToNode.get(key);
    cache.remove(node);
    cache.add(node);
    return node.value;
  }

  public void put(int key, int value) {
    if (keyToNode.containsKey(key)) {
      keyToNode.get(key).value = value;
      get(key);
      return;
    }

    if (cache.size() == capacity) {
      Node lastNode = cache.iterator().next();
      cache.remove(lastNode);
      keyToNode.remove(lastNode.key);
    }

    Node node = new Node(key, value);
    cache.add(node);
    keyToNode.put(key, node);
  }

  private int capacity;
  private Set<Node> cache = new LinkedHashSet<>();
  private Map<Integer, Node> keyToNode = new HashMap<>();
}

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


class LRUCache:
  def __init__(self, capacity: int):
    self.capacity = capacity
    self.keyToNode = {}
    self.head = Node(-1, -1)
    self.tail = Node(-1, -1)
    self.join(self.head, self.tail)

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

    node = self.keyToNode[key]
    self.remove(node)
    self.moveToHead(node)
    return node.value

  def put(self, key: int, value: int) -> None:
    if key in self.keyToNode:
      node = self.keyToNode[key]
      node.value = value
      self.remove(node)
      self.moveToHead(node)
      return

    if len(self.keyToNode) == self.capacity:
      lastNode = self.tail.prev
      del self.keyToNode[lastNode.key]
      self.remove(lastNode)

    self.moveToHead(Node(key, value))
    self.keyToNode[key] = self.head.next

  def join(self, node1: Node, node2: Node):
    node1.next = node2
    node2.prev = node1

  def moveToHead(self, node: Node):
    self.join(node, self.head.next)
    self.join(self.head, node)

  def remove(self, node: Node):
    self.join(node.prev, node.next)