#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;

const int DIM = 1e5 + 5;
const int INF = 1e9;

int n, m, b, nr;
int st[DIM];
int l[6255], r[6255], wh[DIM], mask[DIM];
int a[DIM];
int lg[DIM];
int mn[13][6255];

void build() {
	for (int i = 2; i <= n ; ++i)	
		lg[i] = lg[i >> 1] + 1;
	
	b = lg[n];

	for (int i = 1; i <= n ; i += b) {
		l[++nr] = i; r[nr] = min(i + b - 1, n);
	
		mn[0][nr] = a[i];
		for (int j = l[nr]; j <= r[nr] ; ++j) {
			mn[0][nr] = min(mn[0][nr], a[j]);
			wh[j] = nr;
		}
	}

	for (int k = 1; (1 << k) <= nr ; ++k) 
		for (int i = 1; i + (1 << k) - 1 <= nr ; ++i)
			mn[k][i] = min(mn[k - 1][i], mn[k - 1][i + (1 << (k - 1))]);

	int all = (1 << b) - 1;
	int top = 0;
	for (int i = 1; i <= n ; ++i) {
		mask[i] = ((mask[i - 1] & all) << 1) | 1; 	

		while (top > 0 && a[i] < a[st[top]]) {
			if (st[top] >= i - b)
			mask[i] = mask[i] ^ (1 << (i - st[top])); 
			--top;
		}
		st[++top] = i;
	}
}

int msb(int x) {	
	return 31 - __builtin_clz(x);
}

int query_small(int x, int y) {
	int le = (y - x + 1);
	int myMask = mask[y] & ((1 << le) - 1);
	return a[y - lg[myMask]];
}

int query_big(int x, int y) {
	if (x > y) return INF;
	int le = y - x + 1;
	int k = lg[le], dif = le - (1 << k);
	return min(mn[k][x], mn[k][x + dif]);	
}

int query(int x, int y) {
	int i = wh[x], j = wh[y];
	if (i == j) return query_small(x, y);
	return min({query_small(x, r[i]), query_small(l[j], y), query_big(i + 1, j - 1)});
}

int main() {
	freopen("rmq.in", "r", stdin);
	freopen("rmq.out", "w", stdout);

	scanf("%d%d", &n, &m);
	for (int i = 1; i <= n ; ++i) 
		scanf("%d", &a[i]);
	
	build();
	
	int x, y;
	while (m--) {
		scanf("%d%d", &x, &y);
		if (x > y) swap(x, y);
		printf("%d\n", query(x, y));
	}

	return 0;	
}