曼哈顿交易

• 时间限制：5 秒
• 内存限制：512 MiB

题目描述

有 $N$ 个人排成一行，每个人持有一种股票，第 $i$ 个人持有的股票编号为 $a_i$。不同的人可以持有相同的股票。

在某个区间内，一种股票的“热度”定义为该股票在区间内出现的次数。一次询问给出 $l,r,k$：将区间 $[l,r]$ 内所有不同股票的热度从小到大排列，求第 $k$ 个热度。

若区间内不同股票的种类数少于 $k$，输出 $-1$。

输入格式

第一行包含两个正整数 $N,M$，分别表示人数与询问数。

第二行包含 $N$ 个正整数 $a_1,a_2,\ldots,a_N$。

接下来 $M$ 行，每行包含三个正整数 $l,r,k$，表示一次询问。

输出格式

对每次询问输出一行一个整数，表示答案。

样例输入 1

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

样例输出 1

1
3
2
-1

样例解释

在区间 $[1,4]$ 中，两种股票的热度分别为 $1,3$；在区间 $[1,3]$ 中，两种股票的热度均为 $1,2$ 中对应的出现次数，因此后两个询问的答案分别为 $2,-1$。

数据范围

对于所有数据，$1\le N,M\le10^5$，$1\le a_i\le10^9$，$1\le l\le r\le N$，$k\ge1$。