type LRUCache struct {
    head *Node
    tail *Node
    cache map[int]*Node
    cap int
}

type Node struct {
    key int
    val int
    prev *Node
    next *Node
}

func newNode(key, val int) *Node {
    return &Node{
        key: key,
        val: val,
    }
}

func Constructor(capacity int) LRUCache {
    head := newNode(0, 0)
    tail := newNode(0, 0)

    head.next = tail
    tail.prev = head

    return LRUCache {
        head: head,
        tail: tail,
        cap: capacity,
        cache: make(map[int]*Node),
    }
}

func (this *LRUCache) Get(key int) int {
    
    if res, ok := this.cache[key]; ok {
        this.remove(res)
        this.insert(res)
        return res.val
    }

    return -1
}

func (this *LRUCache) Put(key int, value int)  {
    
    if res, ok := this.cache[key]; ok {
        this.remove(res)
    }

    if len(this.cache) == this.cap {
        this.remove(this.tail.prev)
    }

    this.insert(newNode(key, value))
}

func (this *LRUCache) insert(node *Node) {
    this.cache[node.key] = node

    tempNext := this.head.next
    node.next = tempNext
    this.head.next = node

    node.prev = this.head
    tempNext.prev = node
}

func (this *LRUCache) remove(node *Node) {
    delete(this.cache, node.key)
    node.prev.next = node.next
    node.next.prev = node.prev
}

/**
 * Your LRUCache object will be instantiated and called as such:
 * obj := Constructor(capacity);
 * param_1 := obj.Get(key);
 * obj.Put(key,value);
 */