Algorithm Class - Selection Sort 3

Time limit3sMemory limit512 MB

Summary

Given a permutation of N distinct values, report the pair of values exchanged at the K-th swap of selection sort, or -1 if fewer than K swaps occur.

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

Problem

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

There is an array A storing N distinct positive integers. Find the numbers swapped in the K-th swap when array A is sorted in ascending order using selection sort.

Help our Seojun, who is worried about time limits because N is very large.

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

selection_sort(A[1..N]) { # sorts 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 ≤ 500,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

Output the two numbers swapped in the K-th swap on one line, smaller number first. If the number of swaps is less than K, output -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
```