Algorithm Class - Merge Sort 2

Seojun is again working as a teaching assistant for the merge sort class. Let us check through a problem whether the students understood what his father taught.

There is an array A storing N distinct positive integers. When array A is sorted in ascending order with merge sort, print array A right after the K-th change to an element of array A.

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

merge_sort(A[p..r]) { # Sort A[p..r] in ascending order.
    if (p < r) then {
        q <- ⌊(p + r) / 2⌋;       # q is the midpoint of p and r
        merge_sort(A, p, q);      # sort the first half
        merge_sort(A, q + 1, r);  # sort the second half
        merge(A, p, q, r);        # merge
    }
}

# Merge A[p..q] and A[q+1..r] so that A[p..r] is in ascending order.
# A[p..q] and A[q+1..r] are already sorted in ascending order.
merge(A[], p, q, r) {
    i <- p; j <- q + 1; t <- 1;
    while (i ≤ q and j ≤ r) {
        if (A[i] ≤ A[j])
        then tmp[t++] <- A[i++]; # tmp[t] <- A[i]; t++; i++;
        else tmp[t++] <- A[j++]; # tmp[t] <- A[j]; t++; j++;
    }
    while (i ≤ q)  # when elements remain in the left part
        tmp[t++] <- A[i++];
    while (j ≤ r)  # when elements remain in the right part
        tmp[t++] <- A[j++];
    i <- p; t <- 1;
    while (i ≤ r)  # store the result into A[p..r]
        A[i++] <- tmp[t++]; 
}

The first line gives the size of array A, N (5 ≤ N ≤ 500,000), and the number of changes, K (1 ≤ K ≤ 108).

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

Print array A right after the K-th change occurs in array A, on one line. If the number of changes is less than K, print -1.