#include <iostream>
#include <unordered_map>

using namespace std;

class LRU
{
public:
    LRU(int capacity)
    {
        n = capacity;
        L = new Node(-1, -1);
        R = new Node(-1, -1);
        L->right = R;
        R->left = L;
    }

    struct Node
    {
        int key;
        int val;
        Node* left;
        Node* right;
        Node(int _k, int _v) : key(_k), val(_v), left(nullptr), right(nullptr) {}
    };

    void insert(Node* p)
    {
        p->left = L;
        p->right = L->right;
        L->right->left = p;
        L->right = p;
    }

    void remove(Node* p)
    {
        p->left->right = p->right;
        p->right->left = p->left;
    }

    int get(int key)
    {
        if (!hash.count(key)) return -1;
        Node* p = hash[key];
        int res = p->val;
        remove(p);
        insert(p);
        return res;
    }

    void put(int key, int value)
    {
        if (hash.count(key))
        {
            Node* p = hash[key];
            p->val = value;
            remove(p);
            insert(p);
        }
        else
        {
            if (hash.size() == n)
            {
                Node* p = R->left;
                hash.erase(p->key);
                remove(p);
                delete p;
            }

            Node* p = new Node(key, value);
            hash[key] = p;
            insert(p);
        }
    }

private:
    int n;
    Node* L;
    Node* R;
    unordered_map<int, Node*> hash;
};

int main()
{
    cout << "Hello World!" << endl;
    return 0;
}