Problem Setter: Abu Quwsar Ohi

Intake 33, Department of CSE

You are given N sorted values and Q queries. Each query consists of three values, l, r, and k. Each query states that you have to find the k’th value from the given input starting from index l to index r. Note that the index of N sorted value starts from index 1.

Input Format

The input starts with an integer N (N <= 10⁵), defining the number of values. The next line contains N sorted values (0 <= values <= 10⁹). The next line contains an integer Q (Q <= 10⁵),  defining the number of queries.

The next Q lines contain three space-separated integer l, r, k, (l <= r and k <= r-l+1) defining that you have to find the k’th element from the input value that lies in index l, to r. By k’th value, it is meant that if you sort the values starting from index l to r, then you have to output the k’th value from the sorted values.

Output Format

For each query, output the k’th value in a separated line.

Explanation:

The second query asks you to find the 2^nd  value from the N input values, starting from the 2^nd index value of the input to the 4^th index value. The sorted values on this index range are 13, 14 15. The 2^nd value is 14, which is the answer to the second query.

Samples