Background

静态区间第K小

Description

给定一个序列，求区间第K小

Format

Input

第一行输入一个n代表序列长度；
第二行输入n个数为序列A；
下一行输入一个Q表示询问组数；
下面Q行每行三个数L,R,K（K<=R-L+1）表示一组询问，问[L,R]中第K小的数。

Output

对于每组询问输出一个Ans。

Sample 1

Input

1
1
1
1 1 1

Output

1

Limitation

1s，233MB

Hint

subtask1[20pts]:n<=1000,Q<=1000
subtask2[40pts]:n<=100000,Q<=100000
subtask3[40pts]:n<=300000,Q<=300000