class LRUCache {
    private:
        deque<pair<int,int>> temp;
        stack<pair<int,int>> s;
        unordered_map<int,int> ans;
        int size;
    public:
        LRUCache(int capacity) {
            size = capacity;
        }

        int get(int key) {
            if(ans.find(key) != ans.end()){
                while(temp.back().first != key){
                    s.push(temp.back());
                    temp.pop_back();
                }
                pair<int,int> a;
                a.first = temp.back().first;
                a.second = temp.back().second;
                temp.pop_back();
                temp.push_front(a);
                while(!s.empty()){
                    temp.push_back(s.top());
                    s.pop();
                }
                return a.second;
            }
            else{
                return -1;
            }
        }

        void put(int key, int value) {
            if(ans.find(key) == ans.end()){
                if(temp.size() == size){
                    ans.erase(temp.back().first);
                    temp.pop_back();
                }
                
                temp.push_front({key,value});
                ans[key] = value;
               
            }
            else{
                while(temp.back().first != key){
                    s.push(temp.back());
                    temp.pop_back();
                }
                pair<int,int> a;
                a.first = temp.back().first;     
                a.second = value;
                temp.pop_back();
                ans.erase(key);
                temp.push_front(a);
                ans[key] = value;
                while(!s.empty()){
                    temp.push_back(s.top());
                    s.pop();
                }
            }
        }
        
};