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

using namespace std;

#define MAXN 100002
#define MAXLOG 16
#define MAXG 12

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

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

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

void df(int nod)
{
	vector<int>::iterator it;
	
	Lv[nod] = Lv[T[nod]] + 1;
	
	Q[++E] = nod;
	First[nod] = E;
	for (it = G[nod].begin(); it != G[nod].end(); ++it){
		df(*it);
		Q[++E] = nod;
		Grup[E/MAXG] |= (1<<(E%MAXG));
	}
}

inline void precalcul()
{
	int mask, i, j, minim;
	int Nr[MAXG];
	
	memset(Nr, 0, sizeof(Nr));
	
	for (mask = 0; mask < (1<<MAXG); ++mask)
		for (i = 0; i < MAXG; ++i){
			Nr[i] = 0; minim = i;
			P[mask][i][i] = i;
			for (j = i+1; j < MAXG; ++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 / MAXG) + 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][MAXG-1] + i * MAXG];
	
	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 / MAXG == y / MAXG){
		Ans = Q[ P[Grup[x/MAXG]][x%MAXG][y%MAXG] + (x/MAXG)*MAXG];
		return;
	}
	
	int grupx, grupy;
	grupx = x / MAXG;
	grupy = y / MAXG;
	
	if (Lv[Ans] > Lv[ Q[ P[Grup[grupx]][x%MAXG][MAXG-1] + grupx * MAXG ] ] )
		Ans = Q[ P[Grup[grupx]][x%MAXG][MAXG-1] + grupx * MAXG ];
	if (Lv[Ans] > Lv[ Q[ P[Grup[grupy]][0][y%MAXG] + grupy * MAXG ] ] )
		Ans = Q[ P[Grup[grupy]][0][y%MAXG] + grupy * MAXG ];
	
	
	x = x / MAXG + 1;
	y = y / MAXG - 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];
	}
}

inline void make_graf(nod *a)
{
	if (a -> st != NULL){
		G[a->val].push_back(a->st->val);
		make_graf(a->st);
	}
	if (a -> dr != NULL){
		G[a->val].push_back(a->dr->val);
		make_graf(a->dr);
	}
}

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
	
	make_graf(rad);
	
	E = -1;
	df(rad->val);
	
	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;
}