# -*- coding: utf-8 -*-
"""

    Сортировка пузырьком O(n^2)

"""
"""
arr = [] # массив, который надо отсортировать, укажи любые элементы
for i in range(len(arr)):
    for j in range(len(arr) - 1):
        if arr[j] > arr[j + 1]:
            buffer = arr[j]
            arr[j] = arr[j + 1]
            arr[j + 1] = buffer
print(arr)
"""


"""

    Бинарный поиск log2(n)

"""
"""
arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] # массив, по которому будет идти поиск, он должен быть отсортирован
needingElement = 5 # элемент, который мы ищем
firstElement, middleElement, lastElement = 0, 0, len(arr) - 1
flag = False # показатель, справился ли алгоритм с работой или нет
while firstElement <= lastElement:
    middleElement = (firstElement + lastElement) // 2
    if arr[middleElement] == needingElement:
        flag = True
        break
    if arr[middleElement] < needingElement: firstElement = middleElement + 1
    else: lastElement = middleElement - 1
if flag: print('Нашел значение', needingElement, '\nВ списке:', arr, '\nИндекс искомого элемента ', middleElement)
else: print("Что-то пошло не так")
"""


"""

    Нахождение максимального подмассива O(n)

"""
"""
arr = [1, 2, 3, 4, 5] # массив, в котором мы будем искать максимальный подмассив
currentSum = maxSum = arr[0]
for i in range(1, len(arr)):
    currentSum = max(currentSum, currentSum + arr[i])
    maxSum = max(currentSum, maxSum)
print(maxSum)
"""


"""

    Решение задачи с ферзем O(1)
    Значения, с помощью которых можно проверить:
    n | result
    ----------
    3   8
    4   44
    5   140
    6   340

"""
"""
n = int(input('Введи максимальное кол-во клеток, которое вмещается вдоль одной стороны: '))
result = (n**4)/2 - (5*n**3)/3 + (3*n**2)/2 - n/3 # тупо формула, которую вывели затроты шахматисты
print(int(result))
"""


"""

    Быстрая сортировка

"""
def quickSort(arr):
    if len(arr) < 2: return arr
    else: