rt，莫队 + 值域分块求调。

#include<bits/stdc++.h>
using namespace std;

const int N = 1e5 + 10;
const int S = 400 + 10;
int n, m, a[N], b[N];
int blk, ans[N];
int pblk, tot, bel[N], sp[S], tp[S], cnt[N], num[S];
struct event{
	int l, r, k, id;
	bool operator < (const event &p) const {
		if(l / blk != p.l / blk)
			return l / blk < p.l / blk;
		return r < p.r;
	} 
} q[N];

void init(){
	tot = sqrt(n), pblk = n / tot + (n % tot ? 1 : 0);
	for(int i=1;i<=n;i++)
		bel[i] = (i - 1) / pblk + 1;
	for(int i=1;i<=tot;i++)
		sp[i] = (i - 1) * pblk + 1, tp[i] = i * pblk;
	tp[tot] = n;
}

void add(int k){
	++cnt[a[k]];
	if(cnt[a[k]] == 1)
		++num[bel[a[k]]];
}

void del(int k){
	--cnt[a[k]];
	if(!cnt[a[k]])
		--num[bel[a[k]]];
}

int query(int k){
	int now;
	for(now=1;now<=tot;now++){
		if(k - num[now] <= 0)
			break;
		k -= num[now];
	}
	if(now == tot + 1)
		return -1;
	for(int j=sp[now];j<=tp[now];j++){
		k -= cnt[j];
		if(k <= 0)
			return cnt[j];
	}
}

int main(){
//	freopen("P3730_1.in", "r", stdin);
	scanf("%d%d", &n, &m);
	for(int i=1;i<=n;i++)
		scanf("%d", &a[i]), b[i] = a[i];
	sort(b + 1, b + 1 + n);
	int len = unique(b + 1, b + 1 + n) - b - 1;
	for(int i=1;i<=n;i++)
		a[i] = lower_bound(b + 1, b + 1 + len, a[i]) - b;
	for(int i=1;i<=m;i++)
		scanf("%d%d%d", &q[i].l, &q[i].r, &q[i].k), q[i].id = i;
	blk = sqrt(n);
	sort(q + 1, q + 1 + m);
	int s = 1, t = 0;
	init();
	for(int i=1;i<=m;i++){
		while(s > q[i].l)
			add(--s);
		while(t < q[i].r)
			add(++t);
		while(s < q[i].l)
			del(s++);
		while(t > q[i].r)
			del(t--);
		ans[q[i].id] = query(q[i].k);
	}
	for(int i=1;i<=m;i++)
		printf("%d\n", ans[i]);
	return 0;
}