Untitled

#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 9;
int tree[4 * N] , n;
void upd(int i , int v , int x = 0, int l = 0 , int r = N){
	if(r - l == 1){ tree[x] = v; return; }
	int mid = (l + r) / 2;
	if(i < mid) upd(i , v , 2 * x + 1 , l , mid);
	else upd(i , v , 2 * x + 2, mid , r);
	tree[x] = min(tree[2 * x + 1] , tree[2 * x + 2]);
}
int qry(int lx , int rx , int lower , int x = 0 ,int l = 0, int r = N){
	if(tree[x] >= lower) return -1;
	if(r <= lx ||  l >= rx) return -1;
 	if(r - l == 1){
 		if(l >= lx && r <= rx) return l;
 		return -1;
 	}
	
	int mid = (l + r) / 2;
 
	int q = qry(lx , rx , lower , 2 * x + 2 , mid , r);
	if(~q) return q;
	return qry(lx , rx , lower , 2 * x + 1 , l , mid);
}
int main(){
	memset(tree , -1 , sizeof tree);
	// freopen("in.txt" , "r" , stdin);
	// freopen("out.txt" , "w" , stdout);
	// freopen("error.txt" , "w" , stderr);
	ios::sync_with_stdio(0); cin.tie(NULL); cout.tie(0);
	cin >> n;
	int q; cin >> q;
	int a[n];
	for(int i = 0; i < n; ++i) cin >> a[i];
 
	int ans[q];
	vector<array<int,3>> query[n];
	for(int i = 0; i < q; ++i){
		int l , r , x; cin >> l >> r >> x;
		--l; --r;
		query[r].push_back({l , x , i});
	}
	for(int i = 0; i < n; ++i){
		upd(a[i] , i);
		for(auto &[l , x , idx] : query[i]){
			ans[idx] = qry(0 , x + 1 , l);
		}
	}
	for(int i = 0; i < q; ++i){
		cout << ans[i] << '\n';
	}
	return 0;
}