题目描述

给定一个长度为 $N$ 的整数序列 $A$。有 $Q$ 个询问，每个询问给出 $l,r,k$，请输出子数组 $A_l,A_{l+1},...,A_r$ 中第 $k$ 小的数。

本题用于练习带树状数组的整体二分模板：在值域二分时，用树状数组统计当前左半值域的元素在某个下标区间中出现了多少个。

输入格式

第一行两个整数 $N, Q$。

第二行 $N$ 个整数 $A_i$。

接下来 $Q$ 行，每行三个整数 $l, r, k$。

输出格式

输出 $Q$ 行，第 $i$ 行为第 $i$ 个询问的答案。

数据范围

• $1 \le N,Q \le 2 * 10^5$
• $-10^9 \le A_i \le 10^9$
• $1 \le l \le r \le N$
• $1 \le k \le r-l+1$

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

1
3
3
9