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

class InParser {
	
private:
	
	FILE *fin;
	
	char *buff;
	
	int sp;
	
 
	
	char read_ch() {
	
		++sp;
	
		if (sp == 4096) {
	
			sp = 0;
	
			fread(buff, 1, 4096, fin);
	
		}
	
		return buff[sp];
	
	}
	
 
	
public:
	
	InParser(const char* nume) {
	
		fin = fopen(nume, "r");
	
		buff = new char[4096]();
	
		sp = 4095;
	
	}
	
	
	
	InParser& operator >> (int &n) {
	
		char c;
	
		while (!isdigit(c = read_ch()) && c != '-');
	
		int sgn = 1;
	
		if (c == '-') {
	
			n = 0;
	
			sgn = -1;
	
		} else {
	
			n = c - '0';
	
		}
	
		while (isdigit(c = read_ch())) {
	
			n = 10 * n + c - '0';
	
		}
	
		n *= sgn;
	
		return *this;
	
	}
	
	
	
	InParser& operator >> (long long &n) {
	
		char c;
	
		n = 0;
	
		while (!isdigit(c = read_ch()) && c != '-');
	
		long long sgn = 1;
	
		if (c == '-') {
	
			n = 0;
	
			sgn = -1;
	
		} else {
	
			n = c - '0';
	
		}
	
		while (isdigit(c = read_ch())) {
	
			n = 10 * n + c - '0';
	
		}
	
		n *= sgn;
	
		return *this;
	
	}
	
};

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() {
	InParser fin("rmq.in");
	freopen("rmq.out", "w", stdout);

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

	return 0;	
}