from collections import OrderedDict

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

class LRUCache(object):
    def _add(self, node):
        """Adds into the end of doulbe linked list.
           O(1)
        """
        prev = self.tail.prev
        node.next = self.tail
        node.prev = prev
        self.tail.prev = node
        prev.next = node
        
    def _remove(self, node):
        """Remove from random place node from list.
            O(1)
        """
        node.prev.next = node.next
        node.next.prev = node.prev
    
    def __init__(self, capacity):
        self.nodes = dict()
        self.head = Node(0, 0)
        self.tail = Node(0, 0)
        self.tail.prev = self.head
        self.head.next = self.tail
        self.capacity = capacity

    def get(self, key):
        if key not in self.nodes:
            return -1
        node = self.nodes[key]
        self._remove(node)
        self._add(node)
        return node.value

    def put(self, key, value):
        if key in self.nodes:
            self._remove(self.nodes[key])
        elif len(self.nodes) == self.capacity:
            first = self.head.next
            next_first = first.next
            self.head.next = next_first
            next_first.prev = self.head
            del self.nodes[first.key]
        node = Node(key, value)
        self.nodes[key] = node
        self._add(node)