题目背景

loidc 喜欢大海。在他放假的时候他经常一个人跑到海边独自玩耍。

在浪花的冲击下，他可以忘记打代码的烦躁，真是惬意极了。

虽然今天是周六，但今天可是 $2014$ 年 $11$ 月 $8$ 日，NOIP 2014 复赛 Day 1。在早晨放松之余他可不能忘掉 OI 知识。

题目描述

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

他的命令是这样输入的：

$$\texttt{x y k}$$

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

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

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

输入格式

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

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

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

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

输出格式

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

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

3
1
3

提示

对于 $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$。