Algorithm Class - Quick Sort 2

Seojun is once again a teaching assistant for the quick sort class. Let us check through a problem whether the students understood what his father taught in class.

There is an array A storing N distinct positive integers. When A is sorted in ascending order with quick sort, print the array A immediately after the K-th exchange of two elements of A.

The pseudocode for quick sort on an array of size N is as follows.

quick_sort(A[p..r]) { # sorts A[p..r] in ascending order
    if (p < r) then {
        q <- partition(A, p, r);  # partition
        quick_sort(A, p, q - 1);  # sort the left subarray
        quick_sort(A, q + 1, r);  # sort the right subarray
    }
}

partition(A[], p, r) {
    x <- A[r];    # pivot
    i <- p - 1;   # i is the end point of the elements less than or equal to x
    for j <- p to r - 1  # j is the start point of the elements not yet decided
        if (A[j] ≤ x) then A[++i] <-> A[j]; # increase i, then swap A[i] <-> A[j]
    if (i + 1 != r) then A[i + 1] <-> A[r]; # if i + 1 and r differ, swap A[i + 1] and A[r]
    return i + 1;
}

The first line gives the size of array A, N (5 ≤ N ≤ 10,000), and the number of exchanges, K (1 ≤ K ≤ 10^8).

The next line gives the distinct elements of array A, A1, A2, ..., AN. (1 ≤ Ai ≤ 10^9)

Print the array A immediately after the K-th exchange occurs in array A, on one line. If fewer than K exchanges occur, print -1.