struct Node {
    int key;
    int val;
    Node* next;
    Node* prev;
    Node(int key, int val) : key(key), val(val), next(nullptr), prev(nullptr){}
};

class LRUCache {
public:
    int cap;
    Node* head = new Node(-1, -1);
    Node* tail = new Node(-1, -1);

    unordered_map<int, Node*> kv;

    LRUCache(int capacity) {
        this->cap = capacity;
        head->next = tail;
        tail->prev = head;
    }

    void removeNode(Node* curr) {
        // prev -> curr -> next;
        Node* prev = curr->prev;
        Node* next = curr->next;
        prev->next = next;
        next->prev = prev;
    }

    void addNode(Node* curr) {
        // head -> next;
        Node* next = head->next;
        head->next = curr;
        curr->prev = head;
        curr->next = next;
        next->prev = curr;
    }
    
    // If not found, return -1
    // If found,
    //  1. Move to the head
    int get(int key) {
        if(kv.find(key) == kv.end()) return -1;
        
        Node* node = kv[key];
        removeNode(node);
        addNode(node);
        return node->val;
    }
    
    // If found, move to head
    // else
    //   if meet capacity, remove tail->prev and add newNode
    void put(int key, int value) {
        if(kv.find(key) != kv.end()){
            Node* node = kv[key];
            node->val = value;
            removeNode(node);
            addNode(node);
            return;
        }

        if(kv.size() == cap){
            Node* garbage = tail->prev;
            kv.erase(tail->prev->key);
            removeNode(tail->prev);
            delete garbage;
        }

        Node* newNode = new Node(key, value);
        addNode(newNode);
        kv[key] = newNode;
    }
};