区间k大数查询

题目描述

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

输入格式

第一行包含一个数 $n$，表示序列长度。 第二行包含 $n$ 个正整数，表示给定的序列。 第三个包含一个正整数 $m$，表示询问个数。 接下来 $m$ 行，每行三个数 $l,r,K$，表示询问序列从左往右第 $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$。

来源

童程童美