P2310 loidc, Look at the Sea

loidc likes the sea. When he is on vacation, he often goes to the seaside alone to play. Under the impact of the surf, he can forget the irritation of coding. How pleasant it is. Although today is Saturday, it is $2014$-$11$-$8$, NOIP 2014 Final Round Day 1. While relaxing in the morning, he must not forget OI knowledge.

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: $$\texttt{x y k}$$ 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.

- 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 $m$ lines, each being the answer to one query.

- 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