Kth Smallest Element

You are given an array of n integers and an integer k. Your task is to find the k-th smallest element in the array. This problem can be solved efficiently using the Quickselect algorithm.

The k-th smallest element is defined such that when the array is sorted, it is the element at index k-1. In mathematical notation, if the sorted array is \(A\), you need to find \(A[k-1]\).

Note that the array may contain duplicate elements. The solution must handle the input from standard input (stdin) and print the output to standard output (stdout).

inputFormat

The input is given via standard input with the following format:

n
a1 a2 a3 ... an
k

where:

• n is the number of elements in the array.
• a1 a2 ... an are the space-separated integers.
• k is the order of the smallest element to find (1-indexed).

outputFormat

Output the k-th smallest element to standard output.

6
7 10 4 3 20 15
3

7