class LRUCache: public Cache {
public:
    // Constructor: Initialize LRU cache with given capacity
    LRUCache(int capacity) {
        assert(capacity > 0); // Capacity must be positive
        cp = capacity;
        // Initialize sentinel nodes (dummy head and tail)
        head = new Node(-1, -1);  // Dummy head node
        tail = new Node(-1, -1);  // Dummy tail node
        // Link head and tail to form empty list
        tail->prev = head;
        head->next = tail;
    };

    // Destructor: Clean up all allocated nodes
    ~LRUCache() {
        Node* p = head->next;
        while (p != tail) {
            Node* temp = p;
            p = p->next;
            delete temp;  // Delete all nodes including sentinels
        }
        delete head;
        delete tail;
    }

    // Set key-value pair in cache
    void set(int key, int val) override {
        // Step 1: Check if key exists
        auto p = mp.find(key);
        if (p == mp.end()) {
            // Step 2: If cache is full, evict LRU item
            if (mp.size() == cp)
                popEnd();
            // Create new node and add to map
            mp[key] = new Node(key, val);
        } else {
            // Update existing value
            mp[key]->value = val;
        }
        // Step 3: Move node to front (MRU position)
        moveToFront(mp[key]);
    }
    
    // Get value by key, returns -1 if not found
    int get(int key) override {
        auto p = mp.find(key);
        if (p == mp.end())
            return -1;
        // Move accessed node to front (MRU position)
        moveToFront(mp[key]);
        return mp[key]->value;
    }

private:
    // Move node to front of list (MRU position)
    void moveToFront(Node* curr) {
        // If node is not new, remove from current position
        if (curr->prev) {
            curr->prev->next = curr->next;
            curr->next->prev = curr->prev;
        }
        // Insert node after head (new MRU position)
        Node* headNext = head->next;
        insertNode(head, headNext, curr);
    }
    
    // Helper to insert node between left and right nodes
    void insertNode(Node* left, Node* right, Node* curr) {
        left->next = curr;
        curr->prev = left;
        right->prev = curr;
        curr->next = right;
    }
    
    // Remove LRU item (node before tail)
    void popEnd() {
        Node* end = tail->prev;
        mp.erase(end->key);  // Remove from map
        // Remove from list
        end->prev->next = tail;
        tail->prev = end->prev;
        delete end;  // Free memory
    }
};

class LRUCache : public Cache
{
    Node* _find(int key)
    {
        auto n = mp.find(key);
        if (n == mp.end()) return nullptr;
        return n->second;
    }
    
    Node* _push(int key, int value)
    {
        if (head == nullptr)
        {
            head = tail = new Node(key, value);
            mp[key] = head;
        }
        else 
        {
            auto second = head;
            head = new Node(nullptr, second, key, value);
            second->prev = head;
            mp[key] = head;
        }
        cp--;
        return head;
    }
    
    void _bringToFront(Node* node)
    {
        if (head == node) return;
        
        auto prev = node->prev, next = node->next;
        if (next) next->prev = prev;
        if (prev) prev->next = next;
        
        node->prev = nullptr;
        node->next = head;
        head->prev = node;
        
        head = node;
    }
    
    void _pop()
    {
        mp.erase(tail->key);
        
        tail = tail->prev;
        delete tail->next;
        tail->next = nullptr;
        
        cp++;
    }
    
public:
    LRUCache(int capacity)
    {
        cp = capacity;
        head = nullptr;
        tail = nullptr;
    }
    void set(int key, int value)
    {
        auto n = _find(key);
        if (!n) n = _push(key, value);
        else {
            n->value = value;
            _bringToFront(n);
            }
        if (cp < 0) _pop();
    }
    int get(int key)
    {
        auto n = _find(key);
        if (!n) return -1;
        _bringToFront(n);
        return n->value;
    } 
};