class LRUCache {
    private int capacity;
    private int n;
    private DoubleLinkedList pHead,pTail;
    private DoubleLinkedList[] hash;

    private class DoubleLinkedList{
        int key, val;
        DoubleLinkedList prev, next;

        public DoubleLinkedList(int key, int val){
            this.key = key;
            this.val = val;
            this.prev = null;
            this.next = null;
        }
    }

    public LRUCache(int capacity) {
        this.capacity = capacity;
        this.n = 0;
        hash = new DoubleLinkedList[10001];
        pHead = new DoubleLinkedList(-1,0);
        pTail = new DoubleLinkedList(-2,0);
        pHead.next = pTail;
        pTail.prev = pHead;
    }
    
    public int get(int key) {
        DoubleLinkedList node = hash[key];
        if(node==null){
            return -1;
        }
        moveFront(node);
        return node.val;
    }
    
    public void put(int key, int value) {
        DoubleLinkedList node = hash[key];
        if(node == null && n < capacity){
            node = new DoubleLinkedList(key,value);
            hash[key] = node;
            addFront(node);
            n++;
            return;
        }
        if(node ==null && n==capacity){
            node = pTail.prev;
            hash[node.key] = null;
            hash[key] = node;
        }
        node.key = key;
        node.val = value;
        moveFront(node);
    }

    private void moveFront(DoubleLinkedList node){
        node.prev.next = node.next;
        node.next.prev = node.prev;
        addFront(node);
    }

    private void addFront(DoubleLinkedList node){
        node.prev = pHead;
        node.next = pHead.next;
        pHead.next.prev = node;
        pHead.next = node;
    }
}

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