class LRUCache {
public:

    LRUCache(int capacity) {

        sz = capacity;
    }

    int get(int key) {

        auto it = cache.find(key);
        if( it == cache.end()) return -1;
        touch(it);
        return it->second.first;

    }

    void put(int key, int value) {

        auto it = cache.find(key);
        if(it != cache.end()) touch(it);
        else{
            if(sz == (int)q.size())
            {
                cache.erase(q.back());
                q.pop_back();
            }

            q.push_front(key);
        }
     cache[key] = {value, q.begin()};


    }

    private:
    typedef list<int>li;
    typedef pair<int, li::iterator>pii;
    typedef unordered_map<int, pii>ump;

    ump cache;
    li q;
    int sz;

    void touch(ump::iterator it )
    {
        q.erase(it->second.second);
        q.push_front(it->first);
        it->second.second = q.begin();
    }

};

/**
  knakul853
 */