class LRUCache {
public:

    struct Node {
        int val;
        int key;
        struct Node *prev;
        struct Node *next;
    };

    // key, Node
    unordered_map<int, Node*> hash;
    Node *head;
    Node *tail;
    int cap;


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

    ~LRUCache(){
        Node *ptr = head;
        while (ptr != NULL){
            Node *tmp = ptr->next;
            delete ptr;
            ptr = tmp;
        }
    }

    /* void status(){
        Node *ptr = head->next;
        cout << "LL Front: ";
        while (ptr != tail){
            cout << ptr->key << "->";
            ptr = ptr->next;
        }
        cout << "\tLL Back: ";
        ptr = tail->prev;
        while (ptr != head){
            cout << "<-" << ptr->key;
            ptr = ptr->prev;
        }
        cout << "\n";
    } */

    int get(int key) {
        if (hash.find(key) != hash.end()){
            Node *res = hash.find(key)->second;

            // move to front
            res->prev->next = res->next;
            res->next->prev = res->prev;
            res->prev = head;
            res->next = head->next;
            head->next->prev = res;
            head->next = res;
            return res->val;
        } else {
            return -1;
        }
    }

    void put(int key, int value) {
        Node *res;
        if (hash.find(key) == hash.end()){
            res = new Node;
            res->val = value;
            res->key = key;
            res->prev = head;
            res->next = head->next;
            res->next->prev = res;
            head->next = res;
            hash.insert({key, res});
            cap--;
        } else {
            res = hash.find(key)->second;
            res->val = value;

            // move to front
            res->prev->next = res->next;
            res->next->prev = res->prev;
            res->prev = head;
            res->next = head->next;
            head->next->prev = res;
            head->next = res;
        }

        if (cap < 0){
            // invalidate last one if out of capacity
            Node* inv = tail->prev;
            inv->prev->next = tail;
            tail->prev = inv->prev;
            hash.erase(inv->key);
            delete inv;
            cap++;
        }
    }
};

/**
 * Your LRUCache object will be instantiated and called as such:
 * LRUCache* obj = new LRUCache(capacity);
 * int param_1 = obj->get(key);
 * obj->put(key,value);
 */