Find the K-th Smallest Element

You are given an unsorted array of n integers and an integer k. Your task is to find the k-th smallest element in the array. Note that k is 1-indexed, meaning that if the array were sorted in non-decreasing order, the element at position k is the answer.

Mathematically, if the sorted array is \(a_1, a_2, \ldots, a_n\), you need to find \(a_k\) where \(1 \le k \le n\).

Input/Output: You must read input from stdin and output your result to stdout.

inputFormat

The input consists of three lines:

1. The first line contains an integer n (the number of elements in the array).
2. The second line contains n space-separated integers representing the elements of the array.
3. The third line contains the integer k, indicating that you need to find the k-th smallest element (1-indexed).

outputFormat

Output a single integer: the k-th smallest element in the array.

6
7 10 4 3 20 15
3

7