#include <fstream>
#include <vector>
#include <cmath>

using namespace std;

const int maxn = 100010;
int m, n;
int t[maxn], level[maxn], v[maxn], logaritm[maxn], s[maxn];
vector <int> sons[maxn];
int c[maxn][25];
ofstream g("rmq.out");
	
void findLevel(int nod) {
	for (int i = 0; i < sons[nod].size(); i++) {
		level[sons[nod][i]] = level[nod] + 1;
		findLevel(sons[nod][i]);	
	}	
}

int findAncestor(int a, int b) {
	if (level[a] < level[b]) {
		int aux = a;
		a = b;
		b = aux;	
	}
	
	int log = logaritm[level[a]];
	
	for (int i = log; i >= 0; i--)
		if (c[a][i] != -1 && level[c[a][i]] >= level[b])
			a = c[a][i];
	
	if (a == b)
		return a;
	
	for (int i = log; i >= 0; i--) 
		if (c[a][i] != -1 && c[a][i] != c[b][i]) {
			a = c[a][i];
			b = c[b][i];	
		}
		
	return t[a];
}

int buildTree() {
	int top = 0;
	for (int i = 1; i <= n; i++) {
		int k = top;
		while (k > 0 && v[i] < v[s[k]])
			k--;
		if (k > 0)
			t[i] = s[k];
		if (top > k)
			t[s[k+1]] = i;
		s[++k] = i;
		top = k; 	
	}	
	t[s[1]] = -1;
	return s[1];
}

int main() {
	ifstream f("rmq.in");
	
	f >> n >> m;
	
	int x;
	for (int i = 1; i <= n; i++)
		f >> v[i]; 
		
	logaritm[1] = 0;
	x = 2;
	for (int i = 2; i <= n; i++) {
		if (i == x) {
			logaritm[i] = logaritm[i-1] + 1;
			x = x*2;	
		}	
		else 
			logaritm[i] = logaritm[i-1];
	}
	
	x = buildTree();
	
	for (int i = 1; i <= n; i++)
		if (i != x) 
			sons[t[i]].push_back(i);	
		
	level[x] = 1;
	findLevel(x);
	
	for (int i = 1; i <= n; i++)
		for (int j = 1; (1 << j) <= n; j++)
			c[i][j] = -1;
			
	for (int i = 1; i <= n; i++)
		c[i][0] = t[i];
	c[1][0] = -1;
	
	for (int j = 1; (1 << j) <= n; j++)
		for (int i = 1; i <= n; i++)
			if (c[i][j-1] != -1)
				c[i][j] = c[c[i][j-1]][j-1];
	
	
	int a, b;
	for (int li = 1; li <= m; li++) {
		f >> a >> b;
		x = findAncestor(a, b);
		g << v[x] << '\n';
	}
		
	return 0;
}