#include <fstream>
#define MaxN 100001
using namespace std;
fstream fin ("rmq.in", ios::in);
fstream fout("rmq.out", ios::out);

int v[250000];
int n, m,x,y;

void updat(int poz, int val){
	int elem = 1;
	int st = 1, dr = n;
	int mid;
	while (1){
		if (v[elem] == 0 || v[elem] > val) v[elem] = val;
		mid = (st + dr) >> 1;
		if (poz <= mid) {
			elem = elem << 1;
			dr = mid;
		} else {
			elem = 1 + (elem << 1);
			st = mid + 1;
		};
		if (st == dr) {
			v[elem] = val;
			return;
		};
	};
};

int search_it(int elem, int st, int dr){
	if (x <= st && dr <= y) return v[elem];
	int mid = (st + dr) >> 1;
	int val1 = 100001, val2 = 100001;
	if (st <= x && (mid + 1) <= y) 
			val1 = search_it(1 + (elem << 1), mid + 1, dr);
	if (dr >= y && mid >= x)
			val2 = search_it(elem << 1, st, mid);
	if (val1 > val2) return val2; 
	else return val1;	
};

int main(){
	fin>>n>>m;
	for (int i = 1; i <= n; ++i){
		fin>>x;
		updat(i, x);
	};
	for (int i = 1; i <= m; ++i){
		fin>>x>>y;
		
		fout<<search_it(1, 1, n)<<'\n';
	};

	fin.close();
	fout.close();


};