type Node struct {
    key     int
    value   int
    freq    int
    index   int
    pos     int
}

func NewNode(key, value, index int) *Node{
    return &Node{key, value, 1, index, 0}
}

type NodeHeap []*Node

func (h NodeHeap) Len() int { return len(h) }

func (h NodeHeap) Less(i, j int) bool {
    if h[i].freq == h[j].freq {
        return h[i].index < h[j].index
    }
    return h[i].freq < h[j].freq
}

func (h NodeHeap) Swap(i, j int) {
    h[i], h[j] = h[j], h[i]
    h[i].pos = i
    h[j].pos = j
}

func (h *NodeHeap) Push(x interface{}) {
    n := len(*h)
    node := x.(*Node)
    node.pos = n
    *h = append(*h, node)
}

func (h *NodeHeap) Pop() interface{} {
    old := *h
    n := len(old)
    x := old[n-1]
    old[n-1] = nil // avoid mem leak
    x.pos = -1
    *h = old[:n-1]
    return x
}

type LFUCache struct {
    capacity int
    pq *NodeHeap
    cache map[int]*Node
    size int
    index int
}


func Constructor(capacity int) LFUCache {
    return LFUCache{
        pq: &NodeHeap{},
        cache: map[int]*Node{},
        index: 1,
        capacity: capacity,
    }
}

func (this *LFUCache) Get(key int) int {
    node, exists := this.cache[key]
    if !exists {
        return -1
    }
    node.freq++
    node.index = this.index
    this.index++
    heap.Fix(this.pq, node.pos)
    // for i := range *this.pq {
    //     fmt.Printf("%v|%v|%v,", (*this.pq)[i].key, (*this.pq)[i].freq, (*this.pq)[i].index)
    // }
    // fmt.Printf("\n")
    return node.value
}

func (this *LFUCache) Put(key int, value int)  {
    if this.capacity == 0 {
        return
    }
    node, exists := this.cache[key]
    if exists {
        node.value = value
        node.freq++
        node.index = this.index
        this.index++
        heap.Fix(this.pq, node.pos)
    } else {
        if this.size == this.capacity {
            node := heap.Pop(this.pq).(*Node)
            // fmt.Printf("delete %v\n", node.key)
            delete(this.cache, node.key)
            this.size--
        }
        node := NewNode(key, value, this.index)
        this.index++
        heap.Push(this.pq, node)
        this.cache[key] = node
        this.size++
    }
    // for i := range *this.pq {
    //     fmt.Printf("%v|%v|%v,", (*this.pq)[i].key, (*this.pq)[i].freq, (*this.pq)[i].index)
    // }
    // fmt.Printf("\n")
}


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