Find the K-th Smallest Element in Subarrays

In this problem, you are given an array of (n) integers and (q) queries. Each query is represented as a triplet ((l, r, k)), which asks you to find the (k)-th smallest element in the subarray defined by indices (l) to (r) (inclusive). The (k)-th smallest element is the element that would appear in the (k)-th position if the subarray were sorted in non-decreasing order.

For example, given the subarray ([a_l, a_{l+1}, \ldots, a_r]), if we sort it into ([b_1, b_2, \ldots, b_m]), then the answer is (b_k).

Read the input from (stdin) and write your output to (stdout).

inputFormat

The input is given via standard input ((stdin)) and is formatted as follows:
1. The first line contains a single integer (n) ( (1 \leq n \leq 10^5)), 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 a single integer (q) ( (1 \leq q \leq 10^5)), the number of queries.
4. Each of the next (q) lines contains three space-separated integers (l), (r), and (k) (1 \leq l \leq r \leq n, 1 \leq k \leq r-l+1), representing a query.

outputFormat

For each query, output the (k)-th smallest element in the specified subarray on a separate line, writing the answers to standard output ((stdout)).## sample

5
1 5 2 4 3
3
1 3 2
2 5 3
1 5 4

2
4
4