Algorithm Class - Selection Sort 1

Time limit1sMemory limit512 MB

Summary

Simulate selection sort on an array of N distinct positive integers and report the two values swapped at the K-th swap, or -1 if fewer than K swaps occur.

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

Problem

Seojun is assisting a selection sort class again today. Let's check whether the students understood what his father taught through a problem.

There is an array A storing N distinct positive integers. When array A is sorted in ascending order using selection sort, find the two numbers exchanged at the K-th swap to help Seojun.

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] in 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 swap count K (1 ≤ K ≤ N).

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

Output

Print the two numbers exchanged at the K-th swap in one line, starting with the smaller number. 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 3
```
Example 2
Input
```
5 4
3 1 2 5 4
```
Expected output
```
-1
```