Description

loidc plans to take the LOI team members to the seaside to have fun after the exam. So he wants to write a program to let them understand the wave conditions over a period of time.

His command is entered like this:

This asks, within time $[x, y]$, for the unit time index at which the $k$-th smallest wave height occurs.

But when he was just about to open Dev-pas++, loidc found that his computer was broken. Being lazy as always, he asks you for help. He hopes you can finish the program within $1$ second.

Of course, loidc will tell you the wave height for all time indices in advance, so rest assured. As for how he obtained them, that is unknown.

Input Format

• The first line contains an integer $n$, the total number of time indices.
• The second line contains $n$ numbers $a_i$, in order, representing the wave height at each of the $n$ unit time indices. It is guaranteed that all time indices have pairwise distinct wave heights.
• The third line contains an integer $m$, the number of queries.
• The next $m$ lines each contain $3$ integers $x, y, k$, representing one query.

Output Format

Output $m$ lines, each being the answer to one query.

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

3
1
3

Hint

• For $30\%$ of the testdata, $n, m \le 200$.
• Constraints: For $100\%$ of the testdata, $1 \le n, m \le 4000$, $1 \le a_i \le 10^5$ and $a_i$ are pairwise distinct, $1 \le x \le y \le n$, $1 \le k \le y - x + 1$.

Translated by ChatGPT 5