class Node:
    def __init__(self, key, val):
        self.key = key
        self.val = val
        self.prev = None
        self.next = None


class DoubleList:
    def __init__(self):
        # 頭指針、尾指針
        self.head = Node(0, 0)
        self.tail = Node(0, 0)
        self.head.next = self.tail
        self.tail.prev = self.head

        self.lenSize = 0

    # 尾插、頭出、任意刪
    def add_last(self, x):
        x.next = self.tail
        x.prev = self.tail.prev
        self.tail.prev.next = x
        self.tail.prev = x
        self.lenSize += 1

    def pop_head(self):
        if self.lenSize > 0:
            tmp = self.head.next
            self.remove_anywhere(tmp)
            return tmp

    def remove_anywhere(self, x):
        x.prev.next = x.next
        x.next.prev = x.prev
        self.lenSize -= 1

    def get_size(self):
        return self.lenSize


class LRU:
    def __init__(self, cap):
        self.map = {}
        self.cache = DoubleList()
        # 最大容量
        self.cap = cap

    def get(self, key):
        if key in self.map:
            self.make_recently(key)
            return self.map[key].val
        else:
            return -1

    def put(self, key, val):
        if key in self.map:
            self.remove(key)
            self.add_recently(key, val)
            return
        if self.cache.lenSize == self.cap:
            self.remove_least_used()
        self.add_recently(key, val)

    # 對(duì)手機(jī)后臺(tái)的操作
    # 1. 打開(kāi)新應(yīng)用
    def add_recently(self, key, val):
        node = Node(key, val)
        node.prev = self.cache.tail.prev
        self.cache.tail.prev.next = node
        self.cache.tail.prev = node
        node.next = self.cache.tail
        # 放進(jìn)map
        self.map[key] = node

    # 2. 打開(kāi)后臺(tái)應(yīng)用
    def make_recently(self, key):
        node = self.map[key]
        self.cache.remove_anywhere(node)
        self.cache.add_last(node)

    # 3. 劃掉后臺(tái)應(yīng)用
    def remove(self, key):
        node = self.map[key]
        self.cache.remove_anywhere(node)
        self.map.pop(key)

    # 4. 殺后臺(tái)
    def remove_least_used(self):
        tmp = self.cache.pop_head()
        self.map.pop(tmp.key)