Partition Around the Last Value

Partitioning is the heart of quicksort: pick a pivot value and rearrange the list so that everything smaller or equal comes before it and everything bigger comes after it.

Use this exact method (Lomuto's scheme), with the last value as the pivot:

pivot = a[-1]
i = -1
for j in range(len(a) - 1):
    if a[j] <= pivot:
        i += 1
        a[i], a[j] = a[j], a[i]
a[i + 1], a[-1] = a[-1], a[i + 1]

Return [a, i + 1]: the rearranged list and the final position of the pivot. Do not change nums. The result depends on the exact steps above, so follow them exactly.

Examples

Example 1

Input:

partition_array([3, 7, 1, 5])

Output:

[[3, 1, 5, 7], 2]

3 and 1 are <= 5, 7 is not. The pivot goes after them.

Example 2

Input:

partition_array([4])

Output:

[[4], 0]

A single value is already in place at index 0.

Constraints

• 1 <= len(nums) <= 3 * 10**5
• -10**9 <= nums[i] <= 10**9