Algorithm Class - Selection Sort 2

Interview

Time limit1sMemory limit512 MB

Summary

Simulate selection sort on an array and print the array right after the K-th swap, or -1 if fewer than K swaps occur.

Level: Medium4 of 10
Topics: Simulation, Sorting, Array, Implementation
Solved: No attempts yet

Problem

Seojun is assisting in the selection sort class again today. 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 array A is sorted in ascending order with selection sort, print array A immediately after the K-th swap occurs.

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

selection_sort(A[1..N]) { # sort A[1..N] in ascending order
    for last <- N downto 2 {
        find the largest number A[i] among A[1..last]
        if (last != i) then A[last] <-> A[i]  # if last and i differ, swap A[last] and A[i]
    }
}

Input

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

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

Output

Print array A immediately after the K-th swap occurs, on one line. If the number of swaps is less than K, print -1.

Examples2

Example 1
Input
```
5 2
3 1 2 5 4
```
Expected output
```
2 1 3 4 5
```
Example 2
Input
```
5 4
3 1 2 5 4
```
Expected output
```
-1
```