package main

import "fmt"

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

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

func Constructor(capacity int) LRUCache {
	return LRUCache{
		head: nil,
		tail: nil,
		keys: map[int]*Node{},
		cap:  capacity,
		used: 0,
	}
}

func (c *LRUCache) toFront(node *Node) {
	if c.head.key == node.key {
		return
	}

	node.prev.next = node.next
	if node.next == nil {
		c.tail = node.prev
	} else {
		node.next.prev = node.prev
	}

	node.prev = nil
	node.next = c.head
	c.head.prev = node
	c.head = node
}

func (this *LRUCache) Get(key int) int {
	node, ok := this.keys[key]
	if ok {
		this.toFront(node)
		return node.val
	}
	return -1
}

func (this *LRUCache) Put(key int, value int) {
	node, ok := this.keys[key]
	if ok {
		node.val = value
	} else {
		this.used += 1
		if this.used > this.cap {
			this.used -= 1
			delete(this.keys, this.tail.key)
			this.tail = this.tail.prev
			if this.tail != nil {
				this.tail.next = nil
			}
		}
		node = &Node{
			key:  key,
			val:  value,
			next: this.head,
			prev: nil,
		}
		this.keys[key] = node
		if this.tail == nil {
			this.head = node
			this.tail = node
			return
		}
		this.head.prev = node
		this.head = node
		return
	}

	this.toFront(node)
}

func main() {
	mismatches := 0
	lRUCache := Constructor(10)
	lRUCache.Put(10, 13)
	lRUCache.Put(3, 17)
	lRUCache.Put(6, 11)
	lRUCache.Put(10, 5)
	lRUCache.Put(9, 10)
	res6 := lRUCache.Get(13)
	if res6 != -1 {
		fmt.Printf("Mismatch at operation 6 (Get(13)): expected -1, got %d\n", res6)
		mismatches++
	}
	lRUCache.Put(2, 19)
	res8 := lRUCache.Get(2)
	if res8 != 19 {
		fmt.Printf("Mismatch at operation 8 (Get(2)): expected 19, got %d\n", res8)
		mismatches++
	}
	res9 := lRUCache.Get(3)
	if res9 != 17 {
		fmt.Printf("Mismatch at operation 9 (Get(3)): expected 17, got %d\n", res9)
		mismatches++
	}
	lRUCache.Put(5, 25)
	res11 := lRUCache.Get(8)
	if res11 != -1 {
		fmt.Printf("Mismatch at operation 11 (Get(8)): expected -1, got %d\n", res11)
		mismatches++
	}
	lRUCache.Put(9, 22)
	lRUCache.Put(5, 5)
	lRUCache.Put(1, 30)
	res15 := lRUCache.Get(11)
	if res15 != -1 {
		fmt.Printf("Mismatch at operation 15 (Get(11)): expected -1, got %d\n", res15)
		mismatches++
	}
	lRUCache.Put(9, 12)
	res17 := lRUCache.Get(7)
	if res17 != -1 {
		fmt.Printf("Mismatch at operation 17 (Get(7)): expected -1, got %d\n", res17)
		mismatches++
	}
	res18 := lRUCache.Get(5)
	if res18 != 5 {
		fmt.Printf("Mismatch at operation 18 (Get(5)): expected 5, got %d\n", res18)
		mismatches++
	}
	res19 := lRUCache.Get(8)
	if res19 != -1 {
		fmt.Printf("Mismatch at operation 19 (Get(8)): expected -1, got %d\n", res19)
		mismatches++
	}
	res20 := lRUCache.Get(9)
	if res20 != 12 {
		fmt.Printf("Mismatch at operation 20 (Get(9)): expected 12, got %d\n", res20)
		mismatches++
	}
	lRUCache.Put(4, 30)
	lRUCache.Put(9, 3)
	res23 := lRUCache.Get(9)
	if res23 != 3 {
		fmt.Printf("Mismatch at operation 23 (Get(9)): expected 3, got %d\n", res23)
		mismatches++
	}
	res24 := lRUCache.Get(10)
	if res24 != 5 {
		fmt.Printf("Mismatch at operation 24 (Get(10)): expected 5, got %d\n", res24)
		mismatches++
	}
	res25 := lRUCache.Get(10)
	if res25 != 5 {
		fmt.Printf("Mismatch at operation 25 (Get(10)): expected 5, got %d\n", res25)
		mismatches++
	}
	lRUCache.Put(6, 14)
	lRUCache.Put(3, 1)
	res28 := lRUCache.Get(3)
	if res28 != 1 {
		fmt.Printf("Mismatch at operation 28 (Get(3)): expected 1, got %d\n", res28)
		mismatches++
	}
	lRUCache.Put(10, 11)
	res30 := lRUCache.Get(8)
	if res30 != -1 {
		fmt.Printf("Mismatch at operation 30 (Get(8)): expected -1, got %d\n", res30)
		mismatches++
	}
	lRUCache.Put(2, 14)
	res32 := lRUCache.Get(1)
	if res32 != 30 {
		fmt.Printf("Mismatch at operation 32 (Get(1)): expected 30, got %d\n", res32)
		mismatches++
	}
	res33 := lRUCache.Get(5)
	if res33 != 5 {
		fmt.Printf("Mismatch at operation 33 (Get(5)): expected 5, got %d\n", res33)
		mismatches++
	}
	res34 := lRUCache.Get(4)
	if res34 != 30 {
		fmt.Printf("Mismatch at operation 34 (Get(4)): expected 30, got %d\n", res34)
		mismatches++
	}
	lRUCache.Put(11, 4)
	lRUCache.Put(12, 24)
	lRUCache.Put(5, 18)
	res38 := lRUCache.Get(13)
	if res38 != -1 {
		fmt.Printf("Mismatch at operation 38 (Get(13)): expected -1, got %d\n", res38)
		mismatches++
	}
	lRUCache.Put(7, 23)
	res40 := lRUCache.Get(8)
	if res40 != -1 {
		fmt.Printf("Mismatch at operation 40 (Get(8)): expected -1, got %d\n", res40)
		mismatches++
	}
	res41 := lRUCache.Get(12)
	if res41 != 24 {
		fmt.Printf("Mismatch at operation 41 (Get(12)): expected 24, got %d\n", res41)
		mismatches++
	}
	lRUCache.Put(3, 27)
	lRUCache.Put(2, 12)
	res44 := lRUCache.Get(5)
	if res44 != 18 {
		fmt.Printf("Mismatch at operation 44 (Get(5)): expected 18, got %d\n", res44)
		mismatches++
	}
	lRUCache.Put(2, 9)
	lRUCache.Put(13, 4)
	lRUCache.Put(8, 18)
	lRUCache.Put(1, 7)
	res49 := lRUCache.Get(6)
	if res49 != -1 {
		fmt.Printf("Mismatch at operation 49 (Get(6)): expected -1, got %d\n", res49)
		mismatches++
	}
	lRUCache.Put(9, 29)
	lRUCache.Put(8, 21)
	res52 := lRUCache.Get(5)
	if res52 != 18 {
		fmt.Printf("Mismatch at operation 52 (Get(5)): expected 18, got %d\n", res52)
		mismatches++
	}
	lRUCache.Put(6, 30)
	lRUCache.Put(1, 12)
	res55 := lRUCache.Get(10)
	if res55 != -1 {
		fmt.Printf("Mismatch at operation 55 (Get(10)): expected -1, got %d\n", res55)
		mismatches++
	}
	lRUCache.Put(4, 15)
	lRUCache.Put(7, 22)
	lRUCache.Put(11, 26)
	lRUCache.Put(8, 17)
	lRUCache.Put(9, 29)
	res61 := lRUCache.Get(5)
	if res61 != 18 {
		fmt.Printf("Mismatch at operation 61 (Get(5)): expected 18, got %d\n", res61)
		mismatches++
	}
	lRUCache.Put(3, 4)
	lRUCache.Put(11, 30)
	res64 := lRUCache.Get(12)
	if res64 != -1 {
		fmt.Printf("Mismatch at operation 64 (Get(12)): expected -1, got %d\n", res64)
		mismatches++
	}
	lRUCache.Put(4, 29)
	res66 := lRUCache.Get(3)
	if res66 != 4 {
		fmt.Printf("Mismatch at operation 66 (Get(3)): expected 4, got %d\n", res66)
		mismatches++
	}
	res67 := lRUCache.Get(9)
	if res67 != 29 {
		fmt.Printf("Mismatch at operation 67 (Get(9)): expected 29, got %d\n", res67)
		mismatches++
	}
	res68 := lRUCache.Get(6)
	if res68 != 30 {
		fmt.Printf("Mismatch at operation 68 (Get(6)): expected 30, got %d\n", res68)
		mismatches++
	}
	lRUCache.Put(3, 4)
	res70 := lRUCache.Get(1)
	if res70 != 12 {
		fmt.Printf("Mismatch at operation 70 (Get(1)): expected 12, got %d\n", res70)
		mismatches++
	}
	res71 := lRUCache.Get(10)
	if res71 != -1 {
		fmt.Printf("Mismatch at operation 71 (Get(10)): expected -1, got %d\n", res71)
		mismatches++
	}
	lRUCache.Put(3, 29)
	lRUCache.Put(10, 28)
	lRUCache.Put(1, 20)
	lRUCache.Put(11, 13)
	res76 := lRUCache.Get(3)
	if res76 != 29 {
		fmt.Printf("Mismatch at operation 76 (Get(3)): expected 29, got %d\n", res76)
		mismatches++
	}
	lRUCache.Put(3, 12)
	lRUCache.Put(3, 8)
	lRUCache.Put(10, 9)
	lRUCache.Put(3, 26)
	res81 := lRUCache.Get(8)
	if res81 != 17 {
		fmt.Printf("Mismatch at operation 81 (Get(8)): expected 17, got %d\n", res81)
		mismatches++
	}
	res82 := lRUCache.Get(7)
	if res82 != 22 {
		fmt.Printf("Mismatch at operation 82 (Get(7)): expected 22, got %d\n", res82)
		mismatches++
	}
	res83 := lRUCache.Get(5)
	if res83 != 18 {
		fmt.Printf("Mismatch at operation 83 (Get(5)): expected 18, got %d\n", res83)
		mismatches++
	}
	lRUCache.Put(13, 17)
	lRUCache.Put(2, 27)
	lRUCache.Put(11, 15)
	res87 := lRUCache.Get(12)
	if res87 != -1 {
		fmt.Printf("Mismatch at operation 87 (Get(12)): expected -1, got %d\n", res87)
		mismatches++
	}
	lRUCache.Put(9, 19)
	lRUCache.Put(2, 15)
	lRUCache.Put(3, 16)
	res91 := lRUCache.Get(1)
	if res91 != 20 {
		fmt.Printf("Mismatch at operation 91 (Get(1)): expected 20, got %d\n", res91)
		mismatches++
	}
	lRUCache.Put(12, 17)
	lRUCache.Put(9, 1)
	lRUCache.Put(6, 19)
	res95 := lRUCache.Get(4)
	if res95 != -1 {
		fmt.Printf("Mismatch at operation 95 (Get(4)): expected -1, got %d\n", res95)
		mismatches++
	}
	res96 := lRUCache.Get(5)
	if res96 != 18 {
		fmt.Printf("Mismatch at operation 96 (Get(5)): expected 18, got %d\n", res96)
		mismatches++
	}
	res97 := lRUCache.Get(5)
	if res97 != 18 {
		fmt.Printf("Mismatch at operation 97 (Get(5)): expected 18, got %d\n", res97)
		mismatches++
	}
	lRUCache.Put(8, 1)
	lRUCache.Put(11, 7)
	lRUCache.Put(5, 2)
	lRUCache.Put(9, 28)
	res102 := lRUCache.Get(1)
	if res102 != 20 {
		fmt.Printf("Mismatch at operation 102 (Get(1)): expected 20, got %d\n", res102)
		mismatches++
	}
	lRUCache.Put(2, 2)
	lRUCache.Put(7, 4)
	lRUCache.Put(4, 22)
	lRUCache.Put(7, 24)
	lRUCache.Put(9, 26)
	lRUCache.Put(13, 28)
	lRUCache.Put(11, 26)
	if mismatches == 0 {
		fmt.Println("All Gets matched expected outputs!")
	} else {
		fmt.Printf("Total mismatches: %d\n", mismatches)
	}
}