class LRUCache {

    private static final Node EMPTY_NODE = new Node(-1, -1);

    private final int capacity;
    private final Map<Integer, Node> cache;

    public LRUCache(int capacity) {
        this.capacity = capacity;
        this.cache = new HashMap<>(capacity);
    }

    public int get(int key) {
        Node value = cache.getOrDefault(key, EMPTY_NODE);
        if (value != EMPTY_NODE) {
            merge(value);
            toFirst(value);
        }

        return value.value;
    }

    public void put(int key, int value) {
        Node newNode = cache.getOrDefault(key, new Node(key, value));
        Node actualLastNode = EMPTY_NODE.left;
        merge(newNode);
        toFirst(newNode);
        cache.put(newNode.key, newNode);
        if (cache.size() > capacity) {
            merge(actualLastNode);
            cache.remove(actualLastNode.key);
        }
    }

    private void merge(Node node) {
        node.left.right = node.right;
        node.right.left = node.left;
    }

    private void toFirst(Node node) {
        Node first = EMPTY_NODE.right;
        first.left = node;
        node.left = EMPTY_NODE;
        EMPTY_NODE.right = node;
        node.right = first;
    }

    private static class Node {
        private int key;
        private int value;
        private Node left;
        private Node right;

        Node(int key, int value) {
            this.key = key;
            this.value = value;
            this.left = this;
            this.right = this;
        }

        @Override
        public String toString() {
            return "(" + this.key + ", " + this.value + ")";
        }
    }
}

/**
 * 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);
 */