class DLNode {
  constructor(key, value) {
    this.key = key;
    this.value = value;
    this.prev = null;
    this.next = null;
  }
}

// Doubly Linked List with sentinel head/tail (cleaner edge-case handling)
class DoublyLinkedList {
  constructor() {
    // Dummy sentinels — never removed, simplify all insertions/deletions
    this.head = new DLNode(null, null); // Sentinel head
    this.tail = new DLNode(null, null); // Sentinel tail
    this.head.next = this.tail;
    this.tail.prev = this.head;
    this.size = 0;
  }

  // O(1) — Insert node right after head sentinel (most-recently-used position)
  insertFront(node) {
    node.next = this.head.next;
    node.prev = this.head;
    this.head.next.prev = node;
    this.head.next = node;
    this.size++;
  }

  // O(1) — Remove any node given its pointer (no traversal)
  remove(node) {
    node.prev.next = node.next;
    node.next.prev = node.prev;
    node.prev = null;
    node.next = null;
    this.size--;
  }

  // O(1) — Remove the node just before tail sentinel (least-recently-used)
  removeLast() {
    if (this.tail.prev === this.head) return null; // Empty
    const node = this.tail.prev;
    this.remove(node);
    return node;
  }
}

// ─── LRU Cache built on DLL + HashMap ─────────────────────────
class LRUCache {
  #capacity;
  #map = new Map();  // key → node  (O(1) lookup)
  #list = new DoublyLinkedList(); // ordered by recency

  constructor(capacity) { this.#capacity = capacity; }

  // O(1) — Get and mark as most recently used
  get(key) {
    if (!this.#map.has(key)) return -1;
    const node = this.#map.get(key);
    this.#list.remove(node);      // Splice out
    this.#list.insertFront(node); // Move to front (most recent)
    return node.value;
  }

  // O(1) — Put and evict LRU if over capacity
  put(key, value) {
    if (this.#map.has(key)) {
      this.#list.remove(this.#map.get(key));
    } else if (this.#list.size === this.#capacity) {
      const lru = this.#list.removeLast(); // Evict least recently used
      this.#map.delete(lru.key);
    }
    const node = new DLNode(key, value);
    this.#list.insertFront(node);
    this.#map.set(key, node);
  }
}

const cache = new LRUCache(3);
cache.put('a', 1); cache.put('b', 2); cache.put('c', 3);
cache.get('a');    // Moves 'a' to front
cache.put('d', 4); // Evicts 'b' (LRU) — cache is now {a,c,d}
console.log(cache.get('b')); // -1 (evicted)
console.log(cache.get('a')); // 1