Skip to content
UPEEC

K-th Smallest Element

Easy#sorting#heap#quickselect· solved by 0 · time limit 2.0 s

Print the kk-th smallest element (1-based, counting duplicates).

Input

nn, then nn integers, then kk.

Output

The kk-th smallest value.

Constraints

1≤k≤n≤1051 \le k \le n \le 10^5

Sample 1

Input

6
7 10 4 3 20 15
3

Output

7

Sign in or join free to run and submit your solution.