k-th Smallest

Lab C Intermediate 20 points

Read n integers and k. Print the k-th smallest value using a partial selection sort (only k passes).

Input

n, the integers, then k.

Output

One integer.

Example

Input

6
7 2 9 4 1 8
3

Output

Sample input available Sample output available

Editor

Hints

After pass i, a[i] holds the (i+1)-th smallest value.

Solution explanation

Stopping selection sort early gives the k smallest values in O(n·k).

Show solution

#include <stdio.h>

int main() {
    int n, k, a[100];
    scanf("%d", &n);
    for (int i = 0; i < n; i++) scanf("%d", &a[i]);
    scanf("%d", &k);
    for (int i = 0; i < k; i++) {
        int best = i;
        for (int j = i + 1; j < n; j++) {
            if (a[j] < a[best]) best = j;
        }
        int t = a[i];
        a[i] = a[best];
        a[best] = t;
    }
    printf("%d\n", a[k - 1]);
    return 0;
}

Output

Answer