class LRUCache {
    private final int capacity;
    private final LinkedHashMap<Integer, Integer> cache = new LinkedHashMap<>();

    public LRUCache(int capacity) {
        this.capacity = capacity;
    }

    public int get(int key) {
        Integer value = cache.remove(key);
        if(value != null) {
            cache.put(key, value);
            return value;
        }
        return -1;
    }

    public void put(int key, int value) {
        if(cache.remove(key) != null) {
            cache.put(key, value);
            return ;
        }

        if(cache.size() == capacity) {
            int oldestKey = cache.keySet().iterator().next();
            cache.remove(oldestKey);
        }
        cache.put(key, value);
    }
}