from random import randint

def swap(array:[], index1, index2):
    array[index1], array[index2] = array[index2], array[index1]

def partition(array:[], startIndex:int, endIndex:int) -> int:
    pivot = array[endIndex]
    lastLessorIndex = startIndex - 1
    for i in range(startIndex, endIndex):
        if array[i] <= pivot:
            lastLessorIndex += 1
            swap(array, i, lastLessorIndex)
    lastLessorIndex += 1
    swap(array, endIndex, lastLessorIndex)
    return lastLessorIndex

def randomizedPartition(array:[], startIndex:int, endIndex:int) -> int:
    swap(array, endIndex, randint(startIndex, endIndex))
    return partition(array, startIndex, endIndex)

def randomizedSelect(array:[], startIndex:int, endIndex:int, targetOrder:int) -> int:
# targetOrder that begins with 0 serves more like an index.
    if startIndex == endIndex:
        return array[startIndex]
    currentIndex = randomizedPartition(array, startIndex, endIndex)
    targetIndex = startIndex + targetOrder
    if currentIndex == targetIndex:
        return array[currentIndex]
    elif currentIndex < targetIndex:
        return randomizedSelect(array, currentIndex+1, endIndex, \
                targetIndex-currentIndex-1)
    else:
        return randomizedSelect(array, startIndex, currentIndex-1, targetOrder)