class LRUCache{
    private int capacity;
    private HashMap<Integer,Integer> map;
    private LinkedList<Integer> list;
    public LRUCache(int capacity){
        this.capacity = capacity;
        map = new HashMap<>();
        list=new LinkedList<>();
    }

    public int get (int key){
        if(map.containsKey(key)){
            list.remove((Integer) key);
            list.addLast(key);
            return map.get(key);
        }
        return -1;
    }

    public void put(int key, int value){
        if(map.containsKey(key)){
            list.removeFirst();
            list.addLast(key);
            map.put(key,value);
            return ;
        }
        if(list.size()==capacity){
            map.remove(list.removeFirst());
            map.put(key,value);
            list.addLast(key);
        }
        else{
            map.put(key,value);
            list.addLast(key);
        }
    }


}
public class LRU {
    class LRUCache extends LinkedHashMap<Integer,Integer>{
        private int capacity;
        
        public LRUCache(int capacity){
            super(capacity,0.75F,true);
            this.capacity=capacity;
        }
        
        public int get(int key){
            return super.getOrDefault(key,-1);
        }
        
        public void put(int key,int value){
            super.put(key,value);
        }
        
        @Override
        public boolean removeEldestEntry(Map.Entry<Integer,Integer> eldest){
            return size()>capacity;
        }
    }
}