class LRUCache {

    int capacity;
    HashMap<Integer,Integer> map;
    HashMap<Integer,Long> set;
    
    
    public LRUCache(int capacity) {
        this.capacity=capacity;
        set = new HashMap<Integer,Long>(capacity);
        map = new HashMap<Integer,Integer>(capacity);
    }
    
    public int get(int key) {
       if(map.get(key)!=null){
              set.put(key,System.currentTimeMillis());
              return map.get(key);
        }
        return -1;
    }
    
    public void put(int key, int value) {
        if(map.size()<capacity){
            map.put(key,value);
            set.put(key,System.currentTimeMillis());
        }
        else{
            int removeK=0;
          
             long max=System.currentTimeMillis();
                   for (Map.Entry mapElement : set.entrySet()) { 
                       if((long)mapElement.getValue()<max){
                          max = (long)mapElement.getValue();
                          removeK = (int)mapElement.getKey();
                       }
                   }
              
             set.remove(removeK);
             map.remove(removeK);
             map.put(key,value);
             set.put(key,System.currentTimeMillis());
                   }
        
    }
}


// [null,null,null,1,null,-1,null,-1,3,4]
/**
 * Your LRUCache object will be instantiated and called as such:
 * LRUCache obj = new LRUCache(capacity);
 * int param_1 = obj.get(key);
 * obj.put(key,value);
 */