class LRUCache : public Cache {
    
    void removeBack(){
        Node* currTail = tail;
        Node* newTail = tail->prev;
        int key = currTail->key;
        mp.erase(key);
        if(newTail)
            newTail->next = NULL;
        else 
            head = NULL;
        
        delete currTail;
    }
    
    void addNodeFront(int key, int val) {
        if(head){
            Node* newNode = new Node(NULL, head, key, val);
            if(mp.size() == cp)removeBack();
            head->prev = newNode;
            head = newNode;
            mp[key] = newNode; // Update mapping
        }
        else {
            Node* newNode = new Node(key, val);
            tail = head = newNode;
            mp[key] = newNode;
        }
    }
    
    void moveToHead(Node* arg, int newVal){
        Node *next, *prev;
        arg->value = newVal; // Update value
        if(arg == head)return; // If already head do nothing
        
        next = arg->next;
        prev = arg->prev;
        if(prev) // If previous is not NULL
            prev->next = next;
        if(next) // Same for next
            next->prev = prev;
        
        head->prev = arg;
        if(arg == tail)
            tail = arg->prev;
        arg->next = head;
        arg->prev = NULL;
        head = arg;
    }
    
    public:
        LRUCache(const int &cap){cp = cap;}
        void set(int key,int value) {
            if(mp.find(key) != mp.end()){
                if(mp.size() > 1)
                    moveToHead(mp[key], value);
                else 
                    head->value = value;
            }
            else
                addNodeFront(key, value);
        }
        int get(int key) {
            if(mp.find(key) != mp.end()) {
                moveToHead(mp[key], mp[key]->value); // W or w/o passess all tests
                return mp[key]->value;
            }
            else
                return -1;
        }
};