Find K-th Smallest Element using Quickselect

You are given an array of unique integers and a positive integer k. Your task is to use the Quickselect algorithm to find the k-th smallest element in the array.

The Quickselect algorithm is related to QuickSort. It operates by selecting a pivot element and partitioning the array into those less than the pivot and those greater than the pivot. The algorithm then recurses only into the partition that contains the k-th smallest element, leading to an average time complexity of O(n).

Mathematical Formulation:
Given an array \( A = [a_1, a_2, \dots, a_n] \) of unique integers, find the element \( a_k \) such that exactly \( k-1 \) elements in \( A \) are less than \( a_k \). The relation can be written as:

\[ |\{x \in A : x < a_k\}| = k - 1 \]

inputFormat

The input is given via stdin and consists of three lines:

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

outputFormat

Output the k-th smallest element in the array to stdout.

## sample

6
7 10 4 3 20 15
3

7

</p>