#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
struct sd{
	sd* ls;
	sd* rs;
	sd* f[25]={NULL};
	int val,dep;
}tr[N];
struct num{
	int data,val;
}a[N];
int cnt,top;
sd* stk[N];
sd* root;
int n,m;
void lca_pre(){
	queue<sd*> q;
	q.push(root);
	while(q.size()){
		sd* x=q.front();
//		cerr<<x->ls-tr;
		q.pop();
		if(x->ls!=NULL){
			sd* y=x->ls;
			q.push(y);
			y->dep=x->dep+1;
			y->f[0]=x;
			for(int i=1;i<=20;i++) if(y->f[i-1]!=NULL) y->f[i]=y->f[i-1]->f[i-1];
			
		}
		if(x->rs!=NULL){
			sd* y=x->rs;
			q.push(y);
			y->dep=x->dep+1;
			y->f[0]=x;
			for(int i=1;i<=20;i++) if(y->f[i-1]!=NULL) y->f[i]=y->f[i-1]->f[i-1];
		}
	}
}
sd* lca(sd* x,sd* y){
//	cerr<<y->dep<<" ";
	if(x->dep<y->dep) swap(x,y);
	for(int i=20;i>=0;i--){
		if(x->f[i]==NULL) continue;
		if(x->f[i]->dep>=y->dep)
			x=x->f[i];
	}
//	cerr<<x-tr;
	if(x==y) return x;
	for(int i=20;i>=0;i--){
		if(x->f[i]==NULL) continue;
		if(x->f[i]!=y->f[i])
			x=x->f[i],y=y->f[i];
	}
	return x->f[0];
}
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++) scanf("%d",&a[i].val),a[i].data=i;
	for(int i=1;i<=n;i++){
		int k=top;
		while(k&&stk[k]->val>a[i].val) k--;
		if(k) stk[k]->rs=&tr[i];
		if(k<top) tr[i].ls=stk[k+1];
		stk[++k]=&tr[i];
		tr[i].val=a[i].val;
		top=k;
	}
	int maxn=a[1].val;
	
	for(int i=2;i<=n;i++) if(a[i].val<maxn) maxn=a[i].val,root=&tr[i];
	lca_pre();
	for(int x,y,i=1;i<=m;i++){
		scanf("%d%d",&x,&y);
		printf("%d ",lca(&tr[x],&tr[y])->val);
	}
	return 0;
} 

数组开大两倍也不行