from typing import List


def partition(A: List[int], low, high) -> int:
    """divide the list of numbers into two partitions

    return the index of the pivot number

    choosing the rightmost element in the range as pivot 
    (Lomuto partition scheme)
    """
    pivot = A[high]
    i = low - 1
    for j in range(low, high):
        if A[j] <= pivot:
            i += 1
            A[i], A[j] = A[j], A[i]
    A[i+1], A[high] = A[high], A[i+1]
    return i+1