class LRUCache {
    private final int capacity;
    private final Map<Integer, LRUListNode> map;
    private final LRUListNode head;
    private LRUListNode tail;
    private int size;
    public LRUCache(int capacity) {
        this.capacity = capacity;
        this.map = new HashMap<>();
        this.head = new LRUListNode(Integer.MIN_VALUE, Integer.MIN_VALUE);
        this.tail = head;
        this.size = 0;
    }

    public int get(int key) {
        LRUListNode node = map.get(key);
        if (node == null) return -1;
        if (node == tail) tail = node.prev;
        removeNode(node);
        insertFront(node);

        // System.out.print(" got " + node.val + " last = " + tail.val);
        // head.print();
        return node.val;
    }

    public void put(int key, int value) {
        LRUListNode existingNode = map.get(key);
        if (existingNode != null) {
            get(key);
            existingNode.val = value;
            return;
        }


        LRUListNode node = new LRUListNode(key,value);
        map.put(key, node);
        insertFront(node);

        if(++size > capacity)
            removeLast();

        // System.out.print(" Inserted " + key + "=" + value + " last = ");
        // head.print();
    }

    private void insertFront(LRUListNode node) {
        if (head == tail) {
            tail = node;
        }


        node.next = null;
        node.prev = null;

        LRUListNode originalNext = head.next;

        head.next = node;

        node.prev = head;
        node.next = originalNext;

        if (originalNext != null)
            originalNext.prev = node;
    }

    private void removeNode(LRUListNode node) {
        LRUListNode left = node.prev;
        LRUListNode right = node.next;
        if (left != null)
            left.next = right;
        if (right != null)
            right.prev = left;
        node.prev = null;
        node.next = null;
    }

    private void removeLast() {
        map.remove(tail.key);
        LRUListNode prev = tail.prev;
        removeNode(tail);
        prev.next = null;
        tail = prev;
        size--;

    }

    class LRUListNode {
        LRUListNode(int key, int val) {
            this.val = val;
            this.key = key;
        }
        LRUListNode prev;
        LRUListNode next;
        int val;
        int key;
        public void print() {
            for (LRUListNode n = this; n != null; n = n.next) {
                System.out.print("  [" + n.key + "=" + n.val + "]");
            }
            System.out.println(" ");
        }
    }
}

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