SP26319 ILKQUERY - I LOVE Kd-TREES

你被邀请参加 I Love KD-Tree 年会，不过首先你得向他们证明自己真的很了解数据结构，所以他们给了你一个简单的任务！

给定一个包含 $N$ 个数的数组和 $Q$ 个询问, 每个询问包含三个整数 $k,i,l$： - 令 $d$ 为下标从 $0$ 到 $i$ 这些元素中第 $k$ 小的元素（注：如果前 $i+1$ 个元素是非降序排列的，那么 $d$ 就是下标 $k-1$ 的元素）； - 询问的答案为 $d$ 在整个数组中第 $l$ 次出现的下标。如果没有，则答案为 $-1$。

第一行，输入两个整数 $N, Q$。 第二行，$N$ 个整数，表示数组中每个元素的值，可能有重复值，第 $i$ 个整数表示 $a_i$（下标从 $0$ 开始）。 接下来 $Q$ 行，每行三个整数 $k, i, l$，表示一个询问。

对于每个询问，按输入的顺序依次输出询问的答案，一行一个。

数据范围： - $1 \leq N \leq 10^5$，$1 \leq Q \leq 10^5$； - 对于所有 $a_i$，$-10^9 \leq a_i \leq 10^9$； - 对于每个询问均有 $0 < k \leq i \leq N$ 且 $1 \leq l \leq N$。 第一个询问的解释：下标从 $0$ 到 $4$ 的元素是 $\{2,6,7,1,8\}$，第二小的元素是 $2$；询问的是 $2$ 在整个数组中第二次出现的下标，所以答案是 $6$。