//Voroneanu Radu
//RMQ - folosind lca in O(N) pe cartesian tree O_O
//Complexitate : O(N+M)
//Memorie : O(N)
//Timp de lucru : 90 min
//Complexitatea are o constanta mare deci se justifica implementarea doar pt valori mari

#include <stdio.h>
#include <algorithm>
#include <string.h>

using namespace std;

#define MAXN 100002
#define MAXLOG 16
#define MAXG 8

struct nod{
	nod *tata, *st, *dr;
	int val;
};

int B[MAXN];
nod *act, *rad, *aux;
int Lv[MAXN], First[MAXN], Grup[MAXN], lg[MAXN];
int Q[MAXN*2];
int N, M, E;
int i, x, y;
int Ans;
int P[(1<<8)][8][8];
int RMQ[MAXLOG][MAXN/4 + 2];

inline void init(nod *&a)
{
	a -> tata = a -> st = a -> dr = NULL;
	a -> val = 0;
}

void df(nod *n)
{
	Q[++E] = n -> val;
	First[n->val] = E;
	if (n -> st != NULL){
		Lv[n->st->val] = Lv[n->val] + 1;
		df(n->st);
		Q[++E] = n->val;
		Grup[E>>3] |= (1<<(E&7));
	}
	if (n -> dr != NULL){
		Lv[n->dr->val] = Lv[n->val] + 1;
		df(n->dr);
		Q[++E] = n->val;
		Grup[E>>3] |= (1<<(E&7));
	}
	
}

inline void precalcul()
{
	int mask, i, j, minim;
	int Nr[8];
	
	memset(Nr, 0, sizeof(Nr));
	
	for (mask = 0; mask < (1<<8); ++mask)
		for (i = 0; i < 8; ++i){
			Nr[i] = 0; minim = i;
			P[mask][i][i] = i;
			for (j = i+1; j < 8; ++j){
				if (mask & (1<<j)) 
					Nr[j] = Nr[j-1] - 1;
				else 
					Nr[j] = Nr[j-1] + 1;
				if (Nr[minim] > Nr[j])
					minim = j;
				P[mask][i][j] = minim;
			}
		}
}

inline void rmq_grupe()
{
	int i, j, l, W;
	
	W = (E >> 3) + 1;
	
	lg[1] = 0;
	for (i = 2; i < W; ++i)
		lg[i] = lg[i>>1] + 1;
	
	for (i = 0; i < W; ++i)
		RMQ[0][i] = Q[P[Grup[i]][0][7] + (i<<3)];
	
	for (i = 1; (1<<i) <= W; ++i)
		for (j = 0; j < W - (1<<i) + 1; ++j)
		{
			l = 1<<(i-1);
			RMQ[i][j] = RMQ[i-1][j];
			if (Lv[ RMQ[i][j] ] > Lv[ RMQ[i-1][j+l] ])
				RMQ[i][j] = RMQ[i-1][j+l];
		}
}

inline void rmq(int x, int y)
{
	int diff, l, sh;
	
	if (x > y)
		swap(x,y);
	
	if ((x>>3) == (y>>3)){
		Ans = Q[ P[Grup[x>>3]][x&7][y&7] + x-(x&7)];
		return;
	}
	
	int grupx, grupy;
	grupx = x >> 3;
	grupy = y >> 3;
	
	if (Lv[Ans] > Lv[ Q[ P[Grup[grupx]][x&7][7] + (grupx<<3) ] ] )
		Ans = Q[ P[Grup[grupx]][x&7][7] + (grupx<<3) ];
	if (Lv[Ans] > Lv[ Q[ P[Grup[grupy]][0][y&7] + (grupy<<3) ] ] )
		Ans = Q[ P[Grup[grupy]][0][y&7] + (grupy<<3) ];
	
	
	x = (x>>3) + 1;
	y = (y>>3) - 1;
	if (x <= y){
		diff = y - x + 1;
		l = lg[diff];
		sh = diff - (1<<l);
		if (Lv[Ans] > Lv[ RMQ[l][x] ])
			Ans = RMQ[l][x];
		if (Lv[Ans] > Lv[ RMQ[l][x + sh] ])
			Ans = RMQ[l][x + sh];
	}
}

int main()
{
	freopen("rmq.in","r",stdin);
	freopen("rmq.out","w",stdout);
	
	//cartesian tree
	rad = new nod;
	init(rad);
	act = rad;
	
	scanf("%d %d",&N,&M);
	scanf("%d",&x);
	B[1] = x;
	rad -> val = 1;
	
	for (i = 2; i <= N; ++i){
		scanf("%d",&x);
		B[i] = x;
		while (act->tata != NULL && B[act->val] > x)
			act = act->tata;
		aux = new nod;
		init(aux);
		aux -> val = i;
		
		if (B[act -> val] > x){
			aux -> st = act;
			act -> tata = aux;
			act = aux;
		}
		else {
			if (act -> dr != NULL){
				aux -> st = act -> dr;
				act -> dr -> tata = aux;
				act -> dr = aux;
				aux -> tata = act;
				act = aux;
			}
			else {
				act -> dr = aux;
				aux -> tata = act;
				act = aux;
			}
		}
	}
	
	while (rad -> tata != NULL) rad = rad -> tata;
	//cartesian tree
	
	E = -1;
	df(rad);
	
	precalcul();
	
	rmq_grupe();

	for (i = 1; i <= M; ++i){
		scanf("%d %d",&x,&y);
		
		Ans = x;
		
		rmq(First[x], First[y]);
		
		printf("%d\n",B[Ans]);
	}

	return 0;
}