Description

问题描述 给定一个序列，每次询问序列中第$l$个数到第$r$个数中第$K$大的数是哪个。

Format

Input

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

Output

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

Samples

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

4
2

Hints

对于30%的数据，$n,m\leq100$；

对于100%的数据，$n,m\leq1000$； 保证$k\leq(r-l+1)$，序列中的数$\leq10^6$。