def imin(L, k):
    '''Номер наименьшего элемента в списке L, начиная с k-го'''
    # Начнём с k элемента
    m = k
    # Для всех остальных позиций в L
    for i in range(k + 1, len(L)):
    #   Проверим, не меньше него ли элемент в этой позиции
        if L[i] < L[m]:
    #       И если да, запомним эту позицию
            m = i
    # Её и вернём
    return m

def isort(L):
    '''Обменная сортировка списка L по возрастанию'''
    # Для всех позиций, кроме последней
    for i in range(len(L) - 1):
    #   Найти позицию минимума среди элементов, начиная с этой позиции
        m = imin(L, i)
    #   Поменять местами минимальный элемент и элемент в текущей позиции
        L[i], L[m] = L[m], L[i]

def iisort(L):
    '''Обменная сортировка списка L по возрастанию, полная версия'''
    for k in range(len(L) - 1):
        m = k
        for i in range(k + 1, len(L)):
            if L[i] < L[m]:
                m = i
        L[k], L[m] = L[m], L[k]

def binsearch(L, k):
    '''Двоичный поиск k в упорядоченном списке L'''
    # Если длина L — 1
    if len(L) == 1:
    #   Проверяем, что k принадлежит L непосредствекнно
    #   и возвращаем ответ
        return k == L[0]
    # Берём середину списка
    m = len(L) // 2
    # Если эелмент посредине больше k,
    if L[m] > k:
    #   ищем в левой
    #   и возвращаем резульата
        return binsearch(L[:m], k)
    # Иначе ­
    else:
    #   ищем в правой половине L
    #   и возвращаем резульата
        return binsearch(L[m:], k)