type listNode struct {
	key  int
	val  int
	cnt  int
	prev *listNode
	next *listNode
}

type linkedList struct {
	head *listNode
	tail *listNode
}

func newLinkedList() *linkedList {
	head, tail := &listNode{}, &listNode{}
	head.next = tail
	tail.prev = head
	li := &linkedList{head, tail}
	return li
}

func (li *linkedList) remove(node *listNode) {
	node.prev.next = node.next
	node.next.prev = node.prev
}

type LFUCache struct {
	capacity int
	size     int
	min      int
	cache    map[int]*listNode
	freq     map[int]*linkedList
}

func Constructor(capacity int) LFUCache {
	var lfu LFUCache
	lfu.capacity = capacity
	lfu.cache = make(map[int]*listNode)
	lfu.freq = make(map[int]*linkedList)
	return lfu
}

func (this *LFUCache) Get(key int) int {
	if node, ok := this.cache[key]; ok {
		this.touch(node)
		return node.val
	}
	return -1
}

func (this *LFUCache) Put(key int, value int) {
	if this.capacity == 0 {
		return
	} // Can not put new node.
	if node, ok := this.cache[key]; ok {
		this.touch(node)
		node.val = value
		return
	} // If the key already exists, touch it and update the value.
	if this.size == this.capacity {
		li := this.freq[this.min]
		delete(this.cache, li.tail.prev.key)
		li.remove(li.tail.prev)
		if li.head.next == li.tail {
			delete(this.freq, this.min)
		}
		this.size--
	} // If the cache is full, remove the last element in the least freq list.
	newNode := &listNode{key, value, 1, nil, nil}
	this.insert(newNode)
	this.cache[key] = newNode
	this.min = 1
	this.size++ // Then, insert new node.
}

func (this *LFUCache) insert(node *listNode) {
	li := this.freq[node.cnt]
	if li == nil {
		li = newLinkedList()
		this.freq[node.cnt] = li
	}
	node.next = li.head.next
	node.prev = li.head
	li.head.next = node
	node.next.prev = node
}

func (this *LFUCache) touch(node *listNode) {
	li := this.freq[node.cnt]
	li.remove(node)
	if li.head.next == li.tail {
		delete(this.freq, node.cnt)
		if node.cnt == this.min {
			this.min++
		}
	}
	node.cnt++
	this.insert(node)
}

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