#include <iostream>
#include <cstring>
#include <map>
class LRUCache{
public:
    int max_capacity;
    std::map<int,int> mymap;

    LRUCache(int capacity) {
        max_capacity = capacity;
        mymap.clear();
    }

    ~LRUCache() {
        mymap.clear();
    }

    int get(int key) {
        std::map<int,int>::iterator find;

        find = mymap.find(key);
        if(find == mymap.end()){ // check exist
            return -1;
        }

        mymap.erase (find);
        mymap.insert (std::pair<int,int>(find->first,find->second));

        return find->second;
    }

    void set(int key, int value) {
        mymap.erase (key);
        mymap.insert (std::pair<int,int>(key,value));

        if(mymap.size() > max_capacity){
            mymap.erase (mymap.begin());
        }
    }
};