#include <stdio.h>
#include <deque>

using namespace std;
const int  nmax = 103000;
deque <int> C;
int n,m,a[nmax],T[nmax],P[nmax][100],L[nmax];

int transform(){
  	C.push_back(1);
  	
  	int i=2,top=1,kill;
  	while(i<=n){
  		kill=-1;
  		while(a[i]<a[C.back()] && !C.empty()){
  		kill = C.back() ;	C.pop_back();
  		}
  		if(!C.empty()){
  			T[i]=C.back();
  			
  		}
  		else top=i;
  		C.push_back(i);
  		if(kill!=-1){
  			T[kill]=i;
  			
  		}
  		i++; 		
  	}
  	
 //	T[top]=1;
	 return top;
  	
}

void parc1(int nod,int level){
	L[nod]=level;
	for(int i=1;i<=n;i++){
		if(T[i]==nod)parc1(i,level+1);
	}
}

void dfs(){
    int i,j;
    for(i=0;i<=n;i++)
     for(j=0;1<<j<=n;j++)P[i][j]=-1;
    
	for(i=1;i<=n;i++)P[i][0]=T[i];
	
	for(j=1;1<<j<=n;j++)
	  for(i=1;i<=n;i++)
	   if(P[i][j-1]!=-1 )
	    P[i][j] = P[P[i][j-1]][j-1];
}



int lca(int x,int y){

int log,i;
if(L[x]<L[y])swap(x,y);

for(log=1;1<<log<=L[x];log++);log--;


for(i=log;i>=0;i--)
 if(L[x] -(1<<i)>=L[y])x=P[x][i];
 
 if(x==y)return x;
 
 for(i=log;i>=0;i--)
  if (P[x][i]!=-1 && P[x][i]!=P[y][i]){
  	 x = P[x][i]  ; y = P[y][i] ;
  }
  
   
   return T[x];

}



int main(){
freopen("rmq.in","r",stdin);
freopen("rmq.out","w",stdout);
scanf("%ld%ld",&n,&m);
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
}

parc1(transform(),0);
//printf("%d\n",transform());
//for(int i=1;i<=n;i++)printf("%d ",L[i]);
dfs();
int x,y;
for(int i=1;i<=m;i++){
	scanf("%d %d",&x,&y);
	printf("%d\n",a[lca(x,y)]);
}

fclose(stdout); fclose(stdin);
return 0;
}