题目背景

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

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

虽然今天是周六，但今天可是11.8号。在早晨放松之余他可不能忘掉OI知识。

题目描述

loidc准备带着LOI的队员们考完试后到海边玩耍。所以他想写一个程序让队员们了解在一段时间内海浪的情况。他的命令是这样的x y k输入的，这是要询问在时间[x,y]内海浪高度第k小的单位时刻是那个时刻。

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

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

输入格式

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

第二行n个数，一次表示1~n单位时刻海浪的高度。（数据保证各个时刻海浪高度均不相同）

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

接下来m行，每行3个数x y k，表示一个询问。（数据保证k<=y-x+1）

输出格式

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

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

3
1
3

提示

30% n<=200 m<=200

100% n<=4000 m<=4000

海浪高度取值范围1——100000。