1890 - Kth Smallest

問題

長さ$N$の数列$A$が与えられる。
以下の$M$個のクエリに、与えられる順番で処理してください。
$i$番目のクエリは以下の形式で与えられます。

$L_i$ $R_i$ $k_i$

・数列$A$の$L_i$番目から$R_i$番目の中で$k_i$番目に小さい数を出力する。

入力

入力は以下の形式で標準入力から与えられる。

$N$
$A_1$ $A_2$ ... $A_N$
$M$
$L_1$ $R_1$ $k_2$
$L_2$ $R_2$ $k_2$
 :
$L_M$ $R_M$ $k_M$

出力

各クエリの結果を改行区切りで出力してください。

制約

$1 \leq N,M \leq 1.5 \times 10^{4}$

$0 \leq A_i \leq 1.5 \times 10^{4}$

$1 \leq L < R \leq N$

$1 \leq k \leq R-L+1$

入力はすべて整数

部分点

部分点1は以下の制約を満たす。(点数の20%)

$k = 1$

部分点2は以下の制約を満たす。(点数の40%)

$k \leq 2$

入出力例

入力例1

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

出力例1

1
4
1

{3,1,4,1}の中で1番目に小さい数は1です。
{1,4,1,5}の中で3番目に小さい数は4です。
{3,1,4,1,5}の中で2番目に小さい数は1です。

入力例2

9
1 4 1 4 2 1 3 5 6
5
1 2 1
5 8 2
1 6 4
3 7 4
1 9 4

出力例2

1
2
2
3
2

{1,4}の中で1番目に小さい数は1です。
{2,1,3,5}の中で2番目に小さい数は2です。
{1,4,1,4,2,1}の中で4番目に小さい数は2です。
{1,4,2,1,3}の中で4番目に小さい数は3です。
{1,4,1,4,2,1,3,5,6}の中で4番目に小さい数は2です。