Description

loidc 准备带着 LOI 的队员们考完试后到海边玩耍。所以他想写一个程序让队员们了解在一段时间内海浪的情况。

他的命令是这样输入的：

这是要询问在时间 $[x,y]$ 内海浪高度第 $k$ 小的单位时刻是那个时刻。

但是在他刚准备打开 Dev-pas++ 的时候，loidc 发现他的电脑坏掉了。于是一向喜欢偷懒的他就向你求助。他希望你能在 $1$ 秒内完成程序的运行。

当然 loidc 会提前告诉你所有时段海浪的高度，这点你放心。至于他是如何得到的，这就不得而知了。

Input Format

第一行一个整数 $n$，表示总时间段。

第二行 $n$ 个数 $\{a_n\}$，依次表示 $n$ 个单位时刻内海浪的高度。（数据保证各个时刻海浪高度均不相同）

第三行一个整数 $m$，表示有 $m$ 个询问。

接下来 $m$ 行，每行 $3$ 个整数 $x,y,k$，表示一个询问。

Output Format

一共 $m$ 行，是每个询问的回答。

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

3
1
3

Hint

对于 $30\%$ 的数据，$n,m \le 200$。

对于 $100\%$ 的数据，$1 \le n,m \le 4000$，$1 \le a_i \le 10^5$ 且 $a_i$ 两两不等，$1 \le x \le y \le n$，$1 \le k \le y-x+1$。