class ListNode:

    def __init__(self, x):
        self.val = x
        self.pre = None
        self.next = None

class LRUCache:

    def __init__(self, capacity):
        """
        :type capacity: int
        """
        self.capacity = capacity
        self.size = 0
        self.head = ListNode(0)
        self.tail = ListNode(0)
        self.head.next = self.tail
        self.tail.pre = self.head
        self.data = dict()
        self.lru = dict()

    def insert_head(self, node):
        node.pre = self.head
        node.next = self.head.next
        node.next.pre = node
        self.head.next = node

    def move_head(self, key):
        node = self.lru[key]
        node.pre.next = node.next
        node.next.pre = node.pre
        self.insert_head(node)

    def delete(self):
        node = self.tail.pre
        node.pre.next = self.tail
        self.tail.pre = node.pre
        key = node.val
        del self.data[key]
        del self.lru[key]
        del node

    def get(self, key):
        """
        :type key: int
        :rtype: int
        """
        if key in self.data:
            self.move_head(key)
            return self.data[key]
        else:
            return -1

    def put(self, key, value):
        """
        :type key: int
        :type value: int
        :rtype: void
        """
        if key in self.data:
            self.data[key] = value
            self.move_head(key)
        else:
            self.data[key] = value
            node = ListNode(key)
            self.lru[key] = node
            if self.size == self.capacity:
                self.delete()
                self.size -= 1
            self.insert_head(node)
            self.size += 1
