#include <fstream.h>
ifstream fin("rmq.in");
ofstream fout("rmq.out");
struct nod{
	int nr;
	nod *st,*dr;
}*r;
int n,m;
void insert(nod *&r,int nr){
	if(r==0){
		r=new nod;
		r->nr=nr;
		r->st=0;
		r->dr=0;
	}
	else
		if(nr<r->nr)
			insert(r->st,nr);
		else
			if(nr>r->nr)
				insert(r->dr,nr);
}
int find(nod *r,int x,int y){
	if(r){
		if(x<=r->nr){
			if(r->st)
				return find(r->st,x,y);
			return r->nr;
		}
		return find(r->dr,x,y);
	}
}
void read(){
	fin>>n>>m;
	int i,x,y;
	for(i=1;i<=n;i++){
		fin>>x;
		insert(r,x);
	}
	for(i=1;i<=m;i++){
		fin>>x>>y;
		fout<<find(r,x,y)<<'\n';
	}
	fin.close();
}
void write(nod *r){
	if(r){
		write(r->st);
		printf("%d ",r->nr);
		write(r->dr);
	}
}

int main(){
	read();
	fout.close();
	return 0;
	
}