type linkedNode struct {
	key   int
	value int
	next  *linkedNode
}

type LRUCache struct {
	keyToPrev map[int]*linkedNode
	dummy     *linkedNode
	tail      *linkedNode
	capacity  int
	size      int
}

func NewLRUCache(capacity int) *LRUCache {
	dummy := &linkedNode{}
	c := &LRUCache{
		keyToPrev: make(map[int]*linkedNode),
		dummy:     dummy,
		tail:      dummy,
		capacity:  capacity,
	}
	return c
}

func (c *LRUCache) moveToTail(key int) {
	prev := c.keyToPrev[key]
	cur := prev.next

	if cur == c.tail {
		return
	}

	prev.next = prev.next.next
	c.tail.next = cur
	cur.next = nil

	if prev.next != nil {
		c.keyToPrev[prev.next.key] = prev
	}
	c.keyToPrev[cur.key] = c.tail

	c.tail = cur
}

func (c *LRUCache) Get(key int) int {
	if _, ok := c.keyToPrev[key]; !ok {
		return -1
	}
	c.moveToTail(key)
	return c.tail.value
}

func (c *LRUCache) Set(key, value int) {
	if c.Get(key) != -1 {
		c.tail.value = value
		return
	}

	if c.size < c.capacity {
		c.size++
		cur := &linkedNode{
			key:   key,
			value: value,
			next:  nil,
		}
		c.tail.next = cur
		c.keyToPrev[key] = c.tail
		c.tail = cur
		return
	}

	first := c.dummy.next
	delete(c.keyToPrev, first.key)

	first.key = key
	first.value = value
	c.keyToPrev[key] = c.dummy

	c.moveToTail(key)
}

type RandomizedSet struct {
	nums    []int
	num2idx map[int]int
	rand    *rand.Rand
}

func NewRandomizedSet() *RandomizedSet {
	return &RandomizedSet{
		nums:    []int{},
		num2idx: make(map[int]int),
		rand:    rand.New(rand.NewSource(time.Now().UnixNano())),
	}
}

// Insert inserts a value to the set
// Returns true if the set did not already contain the specified element
func (this *RandomizedSet) Insert(val int) bool {
	if _, ok := this.num2idx[val]; ok {
		return false
	}
	this.num2idx[val] = len(this.nums)
	this.nums = append(this.nums, val)
	return true
}

// Remove removes a value from the set
// Returns true if the set contained the specified element
func (this *RandomizedSet) Remove(val int) bool {
	idx, ok := this.num2idx[val]
	if !ok {
		return false
	}

	lastIdx := len(this.nums) - 1
	if idx < lastIdx {
		lastNum := this.nums[lastIdx]
		this.nums[idx] = lastNum
		this.num2idx[lastNum] = idx
	}
	this.nums = this.nums[:lastIdx]
	delete(this.num2idx, val)
	return true
}

// GetRandom get a random element from the set
func (this *RandomizedSet) GetRandom() int {
	return this.nums[this.rand.Intn(len(this.nums))]
}

func FirstUniqueNumber(nums []int, number int) int {
	counter := make(map[int]int)
	for _, num := range nums {
		counter[num]++
		if num == number {
			break
		}
	}
	if _, ok := counter[number]; !ok {
		return -1
	}
	for _, num := range nums {
		if counter[num] == 1 {
			return num
		}
		if num == number {
			break
		}
	}
	return -1
}

type listNode struct {
	num  int
	next *listNode
}

type DataStream struct {
	dummy, tail *listNode
	num2Prev    map[int]*listNode
	duplicates  map[int]bool
}

func NewDataStream() *DataStream {
	node := &listNode{}
	ds := &DataStream{
		dummy:      node,
		tail:       node,
		num2Prev:   make(map[int]*listNode),
		duplicates: make(map[int]bool),
	}
	return ds
}

func (ds *DataStream) Add(num int) {
	if _, ok := ds.duplicates[num]; ok {
		return
	}

	if _, ok := ds.num2Prev[num]; !ok {
		ds.push(num)
		return
	}

	ds.duplicates[num] = true
	ds.remove(num)
}

func (ds *DataStream) push(num int) {
	ds.num2Prev[num] = ds.tail
	newNode := &listNode{
		num: num,
	}
	ds.tail.next = newNode
	ds.tail = newNode
}

func (ds *DataStream) remove(num int) {
	prev := ds.num2Prev[num]
	delete(ds.num2Prev, num)
	prev.next = prev.next.next

	if prev.next != nil {
		ds.num2Prev[prev.next.num] = prev
	} else {
		ds.tail = prev
	}
}

func (ds *DataStream) FirstUnique() int {
	if ds.dummy.next != nil {
		return ds.dummy.next.num
	}
	return -1
}

import "container/heap"

/
 * @param n: An integer
 * @return: return a  integer as description.
 */
func NthUglyNumber(n int) int {
	h := &IntHeap{1}
	heap.Init(h)
	visited := make(map[int]bool)
	var val int
	// for range n {
	for i := 0; i < n; i++ {
		val = heap.Pop(h).(int)
		for _, factor := range []int{2, 3, 5} {
			cand := val * factor
			if !visited[cand] {
				visited[cand] = true
				heap.Push(h, cand)
			}
		}
	}
	return val
}

// An IntHeap is a min-heap of ints.
type IntHeap []int

func (h IntHeap) Len() int           { return len(h) }
func (h IntHeap) Less(i, j int) bool { return h[i] < h[j] }
func (h IntHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }

func (h *IntHeap) Push(x interface{}) {
	// Push and Pop use pointer receivers because they modify the slice's length,
	// not just its contents.
	*h = append(*h, x.(int))
}

func (h *IntHeap) Pop() interface{} {
	old := *h
	n := len(old)
	x := old[n-1]
	*h = old[0 : n-1]
	return x
}

func NthUglyNumber(n int) int {
	uglys := []int{1}

	p2, p3, p5 := 0, 0, 0

	for i := 1; i < n; i++ {
		lastNumber := uglys[i-1]
		for uglys[p2]*2 <= lastNumber {
			p2++
		}
		for uglys[p3]*3 <= lastNumber {
			p3++
		}
		for uglys[p5]*5 <= lastNumber {
			p5++
		}

		nextUgly := min(uglys[p2]*2, uglys[p3]*3, uglys[p5]*5)
		uglys = append(uglys, nextUgly)
	}

	return uglys[n-1]
}

# @param {int} k an integer
def __init__(self, k):
    self.k = k
    self.heap = []
    
# @param {int} num an integer
def add(self, num):
    heapq.heappush(self.heap, num)
    if len(self.heap) > self.k:
        heapq.heappop(self.heap)

# @return {int[]} the top k largest numbers in array
def topk(self):
    return sorted(self.heap, reverse=True)