题目描述

给定一个长度为 $n$ 的正整数序列，进行 $m$ 次查询。每次查询给出一个区间 $[l, r]$ 和一个正整数 $K$，请你输出该区间中从大到小的第 $K$ 大的数。

输入格式

• 第 1 行：一个整数 $n$，表示序列长度；
• 第 2 行：$n$ 个正整数，表示序列；
• 第 3 行：一个整数 $m$，表示查询次数；
• 接下来的 $m$ 行：每行三个整数 $l, r, K$，表示查询区间 $[l, r]$ 内的第 $K$ 大的数。

输出格式

• 输出 $m$ 行，每行一个整数，表示对应查询的答案。

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

4
2

提示

• 对于 30% 的数据，$n, m \leq 100$；
• 对于 100% 的数据，$n, m \leq 1000$；
• 保证 $1 \leq l \leq r \leq n$，$K \leq r - l + 1$；
• 序列中的整数不超过 $10^6$。