Kth Smallest Element in Subarray

You are given an array of n integers and q queries. Each query is specified by three integers l, r, and k and requires you to find the $k^{th}$ smallest element in the subarray from index l to r (inclusive). Note that the array is 1-indexed.

For each query, you should extract the subarray arr[l...r], sort it in non-decreasing order, and then output the element at the k-1 index in the sorted subarray (which corresponds to the kth smallest element).

Example:

Input:
6
5 3 8 6 2 7
1
1 4 2
Output:
5

</p>

Your solution must read input from stdin and produce output to stdout.

inputFormat

The input begins with an integer n representing the number of elements in the array, followed by n space-separated integers. The next line contains an integer q denoting the number of queries. This is followed by q lines, each containing three integers l, r, and k separated by spaces.

Constraints:

• 1 ≤ n, q ≤ 10⁵
• 1 ≤ l ≤ r ≤ n
• 1 ≤ k ≤ r - l + 1

outputFormat

For each query, output a single line containing the kth smallest element in the corresponding subarray.

## sample

6
5 3 8 6 2 7
1
1 4 2

5

</p>