题目描述

给定一个序列，每次询问序列中第$\red{l}$个数到第$\red{r}$个数中第K大的数是哪个。

输入

第一行包含一个数$\red{n}$，表示序列长度。 第二行包含$\red{n}$个正整数，表示给定的序列。 第三个包含一个正整数$\red{m}$，表示询问个数。 接下来m行，每行三个数$\red{l}$,$\red{r}$,$\red{K}$，表示询问序列从左往右第$\red{l}$个数到第$\red{r}$个数中，从大往小第$\red{K}$大的数是哪个。序列元素从$\red{1}$开始标号。

输出

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

输入样例

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

输出样例

4
2

提示

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

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

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