class LRUCache {

    static class Node
    {
        Node next;

        Node prev;

        final int key;

        int value;

        Node( int k, int v)
        {
            key = k;
            value = v;
        }
    }

    final HashMap<Integer, Node> nodes = new HashMap<>();

    private final int capacity;

    Node head;

    Node tail;

    public LRUCache(int cap) {
        capacity = cap;
    }

    public int get(int key) {
        Node node = nodes.get(key);
        if ( node != null ) {
            extract(node);
            pushBack(node);
            return node.value;
        }
        return -1;
    }

    public void put(int key, int value) {
        Node node = nodes.get(key);
        if ( node == null ) {
            node = new Node(key, value);
            nodes.put(key, node);
            pushBack(node);
            if ( nodes.size() > capacity ) {
                node = popFront();
                nodes.remove(node.key);
            }
        } else {
            node.value = value;
            extract(node);
            pushBack(node);
        }
    }

    private void extract( Node node )
    {
        if ( node.prev != null ) {
            node.prev.next = node.next;
        }

        if ( node.next != null ) {
            node.next.prev = node.prev;
        }
        if ( node == tail ) {
            tail = node.prev;
        }

        if ( node == head ) {
            head = node.next;
        }
        node.next = null;
        node.prev = null;
    }

    private void pushBack( Node node )
    {
        if ( tail == null ) {
            head = node;
        } else {
            tail.next = node;
            node.prev = tail;
        }
        tail = node;
    }

    private Node popFront()
    {
        if ( head != null ) {
            Node node = head;
            head = head.next;
            if ( head != null ) {
                head.prev = null;
            } else {
                tail = null;
            }
            node.next = null;
            return node;
        } else {
            return null;
        }
    }
}