Kth Smallest in the Union of an Array and Its Reversal

Given a list of unique integers (A), first construct a new array by concatenating (A) with its reversal (A^R). Then, sort the combined array in non-decreasing order. Your task is to find the (k)-th smallest element in this sorted array. Note that (k) is 1-indexed.

For example, if (A = [2, 4, 1]), then (A^R = [1, 4, 2]) and the combined array is ([2, 4, 1, 1, 4, 2]). After sorting, it becomes ([1, 1, 2, 2, 4, 4]). If (k = 5), the answer is 4.

inputFormat

The input is given via standard input and 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 array (A).
3. The third line contains an integer (k), representing the position (1-indexed) of the element to retrieve from the sorted union of (A) and its reversal.

outputFormat

Output a single integer: the (k)-th smallest element in the sorted union of the given array and its reversal. The output should be written to standard output.## sample

3
2 4 1
5

4