#include <bits/stdc++.h>
using namespace std;

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

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

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[nr][0] = a[i];
		for (int j = l[nr]; j <= r[nr] ; ++j) {
			mn[nr][0] = min(mn[nr][0], a[j]);
			wh[j] = nr;
		}
	}

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

	int all = (1 << b) - 1;
	stack <int> st;
	for (int i = 1; i <= n ; ++i) {
		mask[i] = ((mask[i - 1] & all) << 1) | 1; 	
		while (!st.empty() && a[i] < a[st.top()]) {
			mask[i] = mask[i] ^ (1 << (i - st.top())); 
			st.pop();
		}
		st.push(i);
	}
}

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[x][k], mn[x + dif][k]);	
}

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[x]), query_small(l[y], 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;	
}