collections.defaultdict  # int, list etc
collections.Counter
collections.OrderedDict

# widely used lib
from sortedcontainers import SortedDict, SortedList, SortedSet

from collections import OrderedDict
class LRUCache(OrderedDict):

    def __init__(self, capacity):
        self.capacity = capacity

    def get(self, key):
        if key not in self:
            return - 1
        
        self.move_to_end(key)
        return self[key]

    def put(self, key, value):
        if key in self:
            self.move_to_end(key)
        self[key] = value
        if len(self) > self.capacity:
            self.popitem(last = False)

# Python 3.6+ states that dictionaries will preserve the order.
class LRUCache:
    def __init__(self, capacity: int):
        self.size = capacity
        self.cache = {}

    def get(self, key: int) -> int:
        value = self.cache.get(key, -1)
        if value != -1:
            self.move_to_end(key)
        return value
        
    def put(self, key: int, value: int) -> None:
        if key in self.cache:
            self.move_to_end(key)
        self.cache[key] = value
        if len(self.cache) > self.size:
            self.remove_from_start()
    
    def move_to_end(self, key = None):
            self.cache[key] = self.cache.pop(key)
            
    def remove_from_start(self):
        self.cache.pop(next(iter(self.cache)))


# Dict + Double linked list
class Node:
    def __init__(self, key, val):
        self.key, self.val = key, val
        self.prev = self.next = None

class LRUCache:

    def __init__(self, capacity: int):
        self.cap = capacity
        self.cache = {} # map key to node
        
        # doubly linked list
        self.left, self.right = Node(0, 0), Node(0, 0)
        self.left.next, self.right.prev = self.right, self.left
    
    # remove node from list
    def remove(self, node):
        prev, nxt = node.prev, node.next
        prev.next, nxt.prev = nxt, prev
    
    # insert node at right
    def insert(self, node):
        prev, nxt = self.right.prev, self.right
        prev.next = nxt.prev = node
        node.next, node.prev = nxt, prev
    
    def get(self, key: int) -> int:
        if key in self.cache:
            self.remove(self.cache[key])
            self.insert(self.cache[key])
            return self.cache[key].val
        return -1

    def put(self, key: int, value: int) -> None:
        if key in self.cache:
            self.remove(self.cache[key])
        self.cache[key] = Node(key, value)
        self.insert(self.cache[key])
        
        if len(self.cache) > self.cap:
            # remove LRU from list and delete from hashmap
            lru = self.left.next
            self.remove(lru)
            del self.cache[lru.key]