题目描述

给定 $n$ 个整数，有 $m$ 次询问，请根据每次询问给定的[$L$,$R$]（包括 $L$ 和 $R$ ），求出这个区间中的第 $K$ 大的数值。

输入

第一行输入整数 $n$ 。

第二行，输入 $n$ 个整数。

第三行，输入整数 $m$ 。

接下来 $m$ 行，每行有 $3$ 个整数 $L$, $R$, $K$ ，序列中的数，从 $1$ 开始编号。

输出

总共输出 $m$ 行，每行一个数，表示每次询问的答案。

样例

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

4
2

说明

【数据范围】

对于 $30\%$ 的数据， $n$,$m$<=$100$ ；

对于 $100\%$ 的数据， $n$,$m$<=$1000$ ；

保证 $k$<=$(r-l+1)$ ，序列中的数<=$10$^$6$。