def ins_sort(arr):
    for s_idx in range(1, len(arr)):                          # 1.
        s_val = arr[s_idx]
        for i_idx, c_val in enumerate(arr[:s_idx]):           # 2.
            if s_val < c_val:
                arr[i_idx + 1: s_idx + 1] = arr[i_idx:s_idx]  # 3.
                arr[i_idx] = s_val
                break
    return arr

def range_sum(n):
    """Return `n` + `n-1` + ... + `1`.
    """
    if n > 0:
        return n + range_sum(n-1)
    return 0

def two_exp(n):
    """Recursively calculate `2**n` for `n >= 0`.
    """
    if n > 0:
        return two_exp(n - 1) + two_exp(n - 1)
    return 1

def memo_two_exp(o_n):
    """Memoized recursive calculation of `2**n` for `n >= 0`.
    """
    cache = {0: 1}
    def _two_exp(n):
        if n in cache:
            return cache[n]
        if n > 0:
            cache[n] = _two_exp(n - 1) + _two_exp(n - 1)
        return cache.get(n, 1)
    return _two_exp(o_n)

from collections import deque

dll = deque([1, 2, 3])      # [1, 2, 3]
dll.append(200)             # [1, 2, 3, 200]
dll.appendleft(-789)        # [-789, 1, 2, 3, 200]
dll.pop()                   # [-789, 1, 2, 3]
dll.popleft()               # [1, 2, 3]
dll.extendleft(["A", "B"])  # ["B", "A", 1, 2, 3]
dll.extend(["Y", "Z"])      # ["B", "A", 1, 2, 3, "Y", "Z"]

class LinkedList(object):
    """Custom linked list implementation.
    You probably want `collections.deque` instead.
    """

    class Node(object):
        def __init__(self, data, prev_node=None, next_node=None):
            self.data = data
            self.prev = prev_node
            self.next = next_node

    def __init__(self, iterable=[]):
        """
        Initialize a linked list from an iterable.
        O(n) initialization time.
        """
        self.len = len(iterable)
        iterator = iter(iterable)
        # Create the doubly linked list, requires a forward and backwards pass
        # head to tail iteration, creates tail -> head linked nodes
        while True:
            try:
                cur_val = next(iterator)
                try:
                    t_cur_node = LinkedList.Node(cur_val, prev_node=t_cur_node)
                except NameError:
                    # on the first element, t_cur_node is not defined
                    t_cur_node = LinkedList.Node(cur_val)
            except StopIteration:
                break

        try:
            self.tail = t_cur_node
        except NameError:
            # iterable was empty
            self.tail = None

        # tail to head iteration, creates head -> linked nodes
        head_cur_node = self.tail
        while True:
            try:
                head_cur_node.next = h_cur_node
            except NameError:
                # on the last element, h_cur_node is not defined
                pass
            finally:
                h_cur_node = head_cur_node

            if h_cur_node is None or h_cur_node.prev is None:
                # we've reached the head again
                head_cur_node = h_cur_node
                break
            head_cur_node = h_cur_node.prev

        self.head = head_cur_node

    def append(self, val):
        """
        Append a new value to the right of the linked list.
        O(1) time.
        """
        cur_tail = self.tail
        if cur_tail is None:
            new_tail = LinkedList.Node(val)
            self.head = new_tail
        else:
            new_tail = LinkedList.Node(val, prev_node=cur_tail)
            cur_tail.next = new_tail
        self.tail = new_tail
        self.len += 1

    def pop(self):
        """
        Remove and return an element from the right side of the linked list.
        If no elements are present, raises an IndexError.
        O(1) time.
        """
        if self.tail is None:
            raise IndexError("pop from empty linked list")
        to_pop = self.tail
        self.tail = to_pop.prev
        if self.tail is not None:
            self.tail.next = None
        if to_pop == self.head:
            self.head = None
        self.len -= 1
        return to_pop.data

    def appendleft(self, val):
        """
        Append a new value to the left of the linked list.
        O(1) time.
        """
        cur_head = self.head
        if cur_head is None:
            new_head = LinkedList.Node(val)
            self.tail = new_head
        else:
            new_head = LinkedList.Node(val, next_node=cur_head)
            cur_head.prev = new_head
        self.head = new_head
        self.len += 1

    def popleft(self):
        """
        Remove and return an element from the left side of the linked list.
        If no elements are present, raises an IndexError.
        O(1) time.
        """
        if self.head is None:
            raise IndexError("popleft from empty linked list")
        to_pop = self.head
        self.head = to_pop.next
        if self.head is not None:
            self.head.prev = None
        if to_pop == self.tail:
            self.tail = None
        self.len -= 1
        return to_pop.data

    def index(self, x):
        """
        Return the position of x in the linked list in O(n) time.
        Returns the first match or raises ValueError if not found.
        """
        cur_node = self.head
        idx = 0
        while cur_node and cur_node.data != x:
            cur_node = cur_node.next
            idx += 1
        if cur_node:
            return idx
        raise ValueError(f"{x} is not in linked list")

    def __iter__(self):
        # return a head to tail travelling iterator.
        cur_node = self.head
        while type(cur_node) == LinkedList.Node:
            yield cur_node.data
            cur_node = cur_node.next

    def __len__(self):
        return self.len

# Simple stack, using a list
stack = list()
stack.append("A")  # add to stack
stack.pop()        # remove from stack

# Simple queue, using deque
from collections import deque
lifo_queue = deque()        # LinkedList() will also work
lifo_queue.appendleft("A")  # add to queue
lifo_queue.pop()            # remove from queue

class Graph(object):
    def __init__(self, edges=[], nodes=[]):
        """Construct a simple directional graph.
        Nodes can be inferred from edges.
        All values must be hashable.
        """
        self.data = {}
        for node in nodes:
            self.add_node(node)
        for (from_node, to_node) in edges:
            self.add_edge(from_node, to_node)

    def nodes(self):
        return list(self.data.keys())

    def neighbors(self, node):
        return list(self.data.get(node, []))

    def add_node(self, node):
        if node not in self.data:
            self.data[node] = []

    def add_edge(self, from_node, to_node):
        if from_node in self.data:
            self.data[from_node].append(to_node)
        else:
            self.data[from_node] = [to_node, ]
        self.add_node(to_node)

hm = {}            # dict()
hm["foo"] = "bar"  # {"foo": "bar"}

class HashTable(object):
    """Custom hash table implementation.
    Use the built-in `dict()` and `{}` instead.
    """

    def __init__(self, lut_len=2):
        super(HashTable, self).__init__()

        self.lut_len = lut_len
        self.lut = [[] for _ in range(lut_len)]
        self.keys_len = 0

    def __getitem__(self, key):
        """Ammoritized lookup of O(1)"""
        lut_idx = hash(key) % self.lut_len
        for lut_key, lut_val in self.lut[lut_idx]:
            if lut_key == key:
                return lut_val
        raise KeyError(key)

    def __setitem__(self, key, value):
        """Ammoritized set of O(1)"""
        lut_idx = hash(key) % self.lut_len
        for lut_iidx, (lut_key, _) in enumerate(self.lut[lut_idx]):
            if lut_key == key:
                self.lut[lut_idx][lut_iidx] = (key, value)
                break
        else:
            self.lut[lut_idx].append((key, value))
            self.keys_len += 1

            if self.keys_len > self.lut_len:
                self._rebalance()

    def __delitem__(self, key):
        """Ammoritized delete of O(1)"""
        lut_idx = hash(key) % self.lut_len
        llut_idx = 0
        for lut_key, _ in self.lut[lut_idx]:
            if lut_key == key:
                break
            llut_idx += 1
        self.lut[lut_idx].pop(llut_idx)
        self.keys_len -= 1

    def __contains__(self, key):
        try:
            self[key]
            return True
        except KeyError:
            return False

    def _rebalance(self):
        """Double the lookup table's size"""
        new_lut_len = self.lut_len * 2
        new_lut = [[] for _ in range(new_lut_len)]
        for sub_lut in self.lut:
            for key, value in sub_lut:
                new_lut_idx = hash(key) % new_lut_len
                for new_lut_iidx, (lut_key, _) in enumerate(new_lut[new_lut_idx]):
                    if lut_key == key:
                        new_lut[new_lut_idx][new_lut_iidx] = (key, value)
                        break
                else:
                    # break was not called
                    new_lut[new_lut_idx].append((key, value))
        self.lut_len = new_lut_len
        self.lut = new_lut

from collections import deque


class IteratorBFS(object):
    def __init__(self, graph, start):
        self.graph = graph
        self.to_visit = deque([start, ])
        self.visited = set()

    def __iter__(self):
        while self.to_visit:
            cur = self.to_visit.pop()   # First In, First out
            if cur in self.visited:
                continue
            for neighbor in self.graph.neighbors(cur):
                if neighbor not in self.visited:
                    self.to_visit.appendleft(neighbor)
            self.visited.add(cur)
            yield cur


class IteratorDFS(object):
    def __init__(self, graph, start):
        self.graph = graph
        self.to_visit = deque([start, ])
        self.visited = set()

    def __iter__(self):
        while self.to_visit:
            cur = self.to_visit.popleft()   # First In, Last out
            if cur in self.visited:
                continue
            # reversed to preserve order of edges, but not 100% necessary
            for neighbor in reversed(self.graph.neighbors(cur)):
                if neighbor not in self.visited:
                    self.to_visit.appendleft(neighbor)
            self.visited.add(cur)
            yield cur

g = Graph(
    edges=[
        ("0", "1"),
        ("0", "4"),
        ("0", "5"),
        ("1", "3"),
        ("1", "4"),
        ("2", "1"),
        ("3", "2"),
        ("3", "4"),
    ]
)

iterator = IteratorBFS(g, "0")
# next(iterator)  # Step by step search. "0"
assert list(iterator) == ["0", "1", "4", "5", "3", "2"]

iterator = IteratorDFS(g, "0")
assert list(iterator) == ["0", "1", "3", "2", "4", "5"]

def mergesort(arr):
    """Recursive implementation of Mergesort.
    """
    if len(arr) >= 2:
        left = mergesort(arr[:len(arr) // 2])
        right = mergesort(arr[len(arr) // 2:])

        left_i = 0
        right_i = 0
        merged = []
        while left_i < len(left) and right_i < len(right):
            if left[left_i] > right[right_i]:
                merged.append(right[right_i])
                right_i += 1
            else:
                merged.append(left[left_i])
                left_i += 1
        return merged + left[left_i:] + right[right_i:]
    return arr

def quicksort(m_arr):
    """Recursive implementation of Quicksort."""

    def _partition(arr, lo, hi):
        pos = lo
        for i in range(lo, hi):
            if arr[i] < arr[hi]:
                arr[i], arr[pos] = arr[pos], arr[i]
                pos += 1
        # put the pivot back
        arr[pos], arr[hi] = arr[hi], arr[pos]
        return pos

    def _quicksort(arr, lo=0, hi=None):
        if hi is None:
            hi = len(arr) - 1
        if lo < hi:
            p = _partition(arr, lo, hi)
            _quicksort(arr, lo=lo, hi=p - 1)
            _quicksort(arr, lo=p + 1, hi=hi)

    _quicksort(m_arr)
    return m_arr

def knapsack(constraint, w_vals):
    """
    w_vals is list of 2-tuples (weight, value)
    constraint is int representing maximum weight
    you can only choose an item once
    [.... .. (4, 4), (3, 12), (2, 100)]
    """
    total_value = 0
    for idx, (weight, value) in enumerate(w_vals):
        remaining = constraint - weight
        if remaining >= 0:
            total_value = max(
                total_value,
                knapsack(remaining, w_vals[idx + 1:]) + value
            )
    return total_value

def knapsack_td(td_constraint, td_w_vals):
    """Memoized version of `knapsack`, top-down Dynamic Programming.
    """
    cache = {}

    def _knapsack(constraint, w_vals):
        if (constraint, w_vals) in cache:
            return cache[(constraint, w_vals)]
        total_value = 0
        for idx, (weight, value) in enumerate(w_vals):
            remaining = constraint - weight
            if remaining >= 0:
                total_value = max(
                    total_value,
                    _knapsack(remaining, w_vals[idx + 1:]) + value
                )
        cache[(constraint, w_vals)] = total_value
        return total_value

    return _knapsack(td_constraint, tuple(td_w_vals))

def knapsack_bu(constraint, w_vals):
    """Tabularized version of `knapsack`, bottom-up Dynamic Programming.
    """
    dp = [
        [0 for wv in range(constraint + 1)]
        for c in range(len(w_vals))
    ]

    # Unnecessary, because everything initialized to 0
    # for idx in range(constraint):
    #     # Base case for top row.
    #     # constraint == 0 is 0, as it cannot hold anything.
    #     dp[0][idx] = 0

    for c in range(1, constraint + 1):
        for w_idx in range(len(w_vals)):
            weight, value = w_vals[w_idx]
            if weight <= c:
                # The current weight can be held in the constraint
                dp[w_idx][c] = max(
                    dp[max(0, w_idx-1)][c],                # Previous item at current constraint
                    dp[max(0, w_idx-1)][max(0, c-weight)] + value  # Previous item + constraint diff best
                )
            else:
                # No fit, extend from last best item
                dp[w_idx][c] = dp[w_idx-1][c]
    return dp[len(w_vals) - 1][constraint]