import random
def partition(arr, low, high, pivot_index):
    pivot = arr[pivot_index]
    arr[pivot_index], arr[high] = arr[high], arr[pivot_index]
    store = low

    for i in range(low, high):
        if arr[i] < pivot:
            arr[i], arr[store] = arr[store], arr[i]
            store += 1

    arr[store], arr[high] = arr[high], arr[store]
    return store

def quickselect(arr, k, low=0, high=None):
    arr = arr.copy()
    if high is None:
        high = len(arr) - 1
    if low < 0 or high >= len(arr) or k < low + 1 or k > high + 1:
        raise ValueError("k must identify an element in the selected range.")

    target = k - 1
    while low <= high:
        if low == high:
            return arr[low]

        pivot = partition(arr, low, high, random.randint(low, high))
        if target == pivot:
            return arr[pivot]
        if target < pivot:
            high = pivot - 1
        else:
            low = pivot + 1


def find_kth_element(arr, k, find_largest=False):
    if k < 1 or k > len(arr):
        raise ValueError(f"k must be between 1 and {len(arr)}")
    if find_largest:
        k = len(arr) - k + 1
    return quickselect(arr, k)


def get_median_of_five(group):
    group.sort()
    return group[len(group) // 2]


def select_pivot(arr, low, high):
    if high - low + 1 <= 5:
        group = arr[low:high + 1]
        return low + group.index(get_median_of_five(group))

    medians = []
    for i in range(low, high + 1, 5):
        medians.append(get_median_of_five(arr[i:min(i + 5, high + 1)]))

    median = median_of_medians_select(medians, 0, len(medians) - 1, len(medians) // 2 + 1)
    return next(i for i in range(low, high + 1) if arr[i] == median)


def median_of_medians_select(arr, low, high, k):
    if low < 0 or high >= len(arr) or k < 1 or k > high - low + 1:
        raise ValueError("k must identify an element in the selected range.")
    if low == high:
        return arr[low]

    pivot = partition(arr, low, high, select_pivot(arr, low, high))
    target = low + k - 1
    if target == pivot:
        return arr[pivot]
    if target < pivot:
        return median_of_medians_select(arr, low, pivot - 1, k)
    return median_of_medians_select(arr, pivot + 1, high, target - pivot)


if __name__ == "__main__":
    data = [12, 3, 5, 7, 4, 19, 26, 23, 15, 8, 10, 2]
    k = 4
    smallest = find_kth_element(data, k)
    largest = find_kth_element(data, k, find_largest=True)
    median = median_of_medians_select(data.copy(), 0, len(data) - 1, k)

    print(f"Original array: {data}")
    print(f"Sorted array: {sorted(data)}")
    print(f"{k}-th smallest: {smallest}")
    print(f"{k}-th largest: {largest}")
    print(f"{k}-th smallest (Median-of-Medians): {median}")
