直接贴代码：
#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <algorithm>
using namespace std;
const int NMax=100100;
struct _node {
	bool InTree;
    int key,num,size;
    _node *left,*right;
	inline int lsize(){return left?left->size:0;}
	inline int rsize(){return right?right->size:0;}
};
struct Treap {
	_node *Tree;_node pool[NMax];
	int _L;
	Treap(){Tree=NULL;_L=0;}
	inline _node *_RightR(_node *p,_node *l) {p->left=l->right;l->right=p;p->size=p->lsize()+p->rsize()+1;l->size=l->lsize()+l->rsize()+1;return l;}
	inline _node *_LeftR(_node *p,_node *r) {p->right=r->left;r->left=p;p->size=p->lsize()+p->rsize()+1;r->size=r->lsize()+r->rsize()+1;return r;}
	inline void Ins(int x) {Tree=_Ins(x,Tree);}
	_node* _Ins(int x,_node *p) {
		if(!p){
			p=&pool[_L++];
			p->num=x;p->InTree=1;p->size=1;
			p->key=(rand()<<16)^(rand()<<8)^(rand());
			p->left=p->right=NULL;
			return p;
		}
		if(x>=p->num) {
			p->right=_Ins(x,p->right);
			if(p->right->key<p->key) p=_LeftR(p,p->right);
			p->size=p->lsize()+p->rsize()+1;
		}else{
			p->left=_Ins(x,p->left);
			if(p->left->key<p->key) p=_RightR(p,p->left);
		    p->size=p->rsize()+p->lsize()+1;
        }
		return p;
	}
	inline void Del(int x){if(_Find(x,Tree))Tree=_Del(x,Tree);}
	_node *_Del(int x,_node *p) {
        if(p->num==x) {
            if(!p->left) return p->right;
            else if(!p->right) return p->left;
            else {
                if(p->left->key>p->right->key) {
                    p=_LeftR(p,p->right);p->size--;
					p->left=_Del(x,p->left);
                    return p;
                }else {
                    p=_RightR(p,p->left);p->size--;
                    p->right=_Del(x,p->right);
                    return p;
                }
            }
        }else if(x>p->num) {
            p->size--;p->right=_Del(x,p->right);
            return p;
        }else if(x<p->num) {
            p->size--;p->left=_Del(x,p->left);
            return p;
        }
    }
	inline bool Find(int x) {return _Find(x,Tree);}
	_node *_Find(int x,_node *p) {
		while(p&&(p->num!=x||!p->InTree)) {
			if(x>p->num) p=p->right;
			else p=p->left;
		}
		return p;
	}
	inline int Findidx(int k){_node *tmp=_Findidx(k,Tree);return tmp?tmp->num:(~0u>>1);}
	_node *_Findidx(int k,_node *p) {
		if(p->lsize()+1==k) return p;
		if(k<=p->lsize()) return _Findidx(k,p->left);
		if(k>p->lsize()+1) return _Findidx(k-p->lsize()-1,p->right);
	}
	inline int Lookup() {return _Lookup(Tree);}
	int _Lookup(_node *p){
		int ret=1;
		if(!p->InTree) ret=0;
		if(p->left) ret+=_Lookup(p->left);
		if(p->right) ret+=_Lookup(p->right);
		return ret;
	}
};
int A[NMax],Ans[NMax];
typedef pair<pair<int,int>,pair<int,int> > ppp;
ppp B[NMax];
Treap treap;
bool cmp(ppp a,ppp b) {return a.first.first<b.first.first||(a.first.first==b.first.first&&a.first.second<b.first.second);}
int main()
{
	int N,M,x,y,z;
	scanf("%d%d",&N,&M);
	for(int i=1;i<=N;i++) scanf("%d",A+i);
	for(int i=1;i<=M;i++) {
		scanf("%d%d%d",&x,&y,&z);
		if(x>y) swap(x,y);
		B[i].first.first=x;B[i].first.second=y;
		B[i].second.first=i;B[i].second.second=z;
	}
	sort(B+1,B+M+1,cmp);
	int l=1,r=0;
	for(int i=1;i<=M;i++) {
		while(B[i].first.second>r) treap.Ins(A[++r]);
		while(B[i].first.first>l) treap.Del(A[l++]);
	    Ans[B[i].second.first]=treap.Findidx(B[i].second.second);
	}
	for(int i=1;i<=M;i++) printf("%d\n",Ans[i]);
	getchar();getchar();getchar();
	return 0;
}