// Runtime: 61 ms, faster than 65.05% of Java online submissions for LRU Cache.
// Memory Usage: 57.5 MB, less than 61.35% of Java online submissions for LRU Cache.
class LRUCache {
    Map<Integer, CacheItem> map;
    CacheItem head;
    CacheItem tail;
    int capacity;

    public LRUCache(int capacity) {
        this.capacity = capacity;
        map = new HashMap<Integer, CacheItem>();
        head = null;
        tail = null;
    }

    public int get(int key) {
        CacheItem item = map.get(key);
        if (item == null) return -1;

        use(item);

        return item.val;
    }

    private void use(CacheItem item) {
        if (head == tail) return;
        if (tail == item) return;

        if (item == head) setHead(item.next);
        else item.prev.linkNext(item.next);

        setTail(item);
    }

    public void put(int key, int value) {
        CacheItem item = map.get(key);

        if (item != null) {
            item.val = value;
            use(item);
            return;
        }

        if (map.size() == capacity) evict();

        item = new CacheItem(key, value);
        map.put(key, item);

        if (head == null) setHead(item);

        setTail(item);
    }

    private void evict() {
        map.remove(head.key);

        if (head == tail) tail = null;
        setHead(head.next);
    }

    private void setHead(CacheItem item) {
        head = item;
        if (head != null) head.prev = null;
    }

    private void setTail(CacheItem item) {
        if (tail == item) return;

        if (tail != null) {
            tail.linkNext(item);
            item.next = null;
        }
        tail = item;
    }

    class CacheItem {
        public int key;

        public int val;

        public CacheItem next;

        public CacheItem prev;

        public CacheItem(int key, int value){
            this.key = key;
            this.val = value;
        }

        public void linkNext(CacheItem n) {
            next = n;
            if (n != null) n.prev = this;
        }
    }
}

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