除了#4都WA了，原因都是在不该输出-1时输出了-1

#include<bits/stdc++.h>
#define int long long
#define N 1000005
using namespace std;
struct node{
	int l,r,k,id;
}e[N];
int n,m,cnt,blc,tot[N],bel[N],sum[N],ans[N],a[N],b[N],c[N],mx,tmp; 
bool cmp(node x,node y){
	if(x.l/blc!=y.l/blc) return x.l<y.l;
	return x.r<y.r;
}
void add(int x){
	tot[a[x]]++;
	tmp=tot[a[x]];
	c[tmp-1]--,c[tmp]++;
	bel[tmp]=(tmp-1)/blc+1;
	mx=max(mx,bel[tmp]);
	sum[bel[tmp-1]]--,sum[bel[tmp]]++;
}
void del(int x){
	tot[a[x]]--;
	tmp=tot[a[x]];
	sum[bel[tmp+1]]--,sum[bel[tmp]]++;
	c[tmp+1]--,c[tmp]++;
}
int solve(int x){
	int s=0;
	for(int i=1;i<=mx;i++){
		s+=sum[i];
		if(s>=x){
			s-=sum[i];
			for(int j=(i-1)*blc+1;j<=i*blc;j++){
				s+=c[j];
				if(s>=x) return j;
			}
		}
	}
	return -1;
}
signed main(){
	cin>>n>>m,blc=sqrt(n);
	for(int i=1;i<=n;i++) 
		cin>>a[i],b[i]=a[i];
	sort(b+1,b+n+1);
	cnt=unique(b+1,b+n+1)-(b+1);
	for(int i=1;i<=n;i++)
		a[i]=lower_bound(b+1,b+cnt+1,a[i])-b;
	for(int i=1,l,r,k;i<=m;i++){
		cin>>l>>r>>k;
		e[i]={l,r,k,i};
	}
	sort(e+1,e+m+1,cmp);
	int l=1,r=0;
	for(int i=1;i<=m;i++){
		while(l<e[i].l) del(l++);
		while(l>e[i].l) add(--l);
		while(r<e[i].r) add(++r);
		while(r>e[i].r) del(r--);
		ans[e[i].id]=solve(e[i].k);
	}
	for(int i=1;i<=m;i++) cout<<ans[i]<<endl;
	return 0;
}
/*
5
2 4 3 1 5
3
4 3 
1 3 
3 2
*/