cf622c

#include<bits/stdc++.h>
using namespace std;
const int maxn=2e5+10;
int a[maxn];
int lg[maxn];
int fmax1[maxn][25];
int fmin1[maxn][25]; 
int x[maxn];
int maxx[maxn];
int minn[maxn];
int n,m;
void q1(){
	for(int i=1;i<=n;i++){
		fmax1[i][0]=i;
	}
	for(int i=2;i<=n;i++){
		lg[i]=lg[i/2]+1;
	}
	for(int j=1;(1<<j)<=n;j++){
		for(int i=1;i+(1<<j)-1<=n;i++){
			if(a[fmax1[i][j-1]]<=a[fmax1[i+(1<<(j-1))][j-1]]){
				fmax1[i][j]=fmax1[i+(1<<(j-1))][j-1];
			}else fmax1[i][j]=fmax1[i][j-1];
		}
	}
	return ;
}
void q2(){
	for(int i=1;i<=n;i++){
		fmin1[i][0]=i;
	}
	for(int i=2;i<=n;i++){
		lg[i]=lg[i/2]+1;
	}
	for(int j=1;(1<<j)<=n;j++){
		for(int i=1;i+(1<<j)-1<=n;i++){
			if(a[fmin1[i][j-1]]<=a[fmin1[i+(1<<(j-1))][j-1]]){
				fmin1[i][j]=fmin1[i+(1<<(j-1))][j-1];
			}else fmin1[i][j]=fmin1[i][j-1];
		}
	}
	return ;
}
int out(int l,int r,int shu){
	int len=r-l+1;
	int k=lg[len];
	int ansmax=0,ansmin=0;
	if(a[fmax1[l][k]]<=a[fmax1[r-(1<<k)+1][k]]){
		ansmax=fmax1[r-(1<<k)+1][k];
	}
	else ansmax=fmax1[l][k];
	
	if(a[fmin1[l][k]]<=a[fmin1[r-(1<<k)+1][k]]){
		ansmin=fmin1[r-(1<<k)+1][k];
	}
	else ansmin=fmin1[l][k];
	
//	max(fmax1[l][k]],fmax1[r-(1<<k)+1][k]);
//	min(fmin11[l][k],fmin1[r-(1<<k)+1][k]);
	if(a[ansmax]==shu&&a[ansmin]==shu)return -1;
	else if(a[ansmax]==shu)return ansmin;
	else return ansmax;

}
int main(){
    ios::sync_with_stdio(0),cin.tie(0);
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	q1();
	q2();
	for(int i=1;i<=m;i++){
		int l,r;
		cin>>l>>r>>x[i];
		cout<<out(l,r,x[i])<<endl;
	}


	return 0;
}