#include <cstdio>
#include <vector>
#include <string>

using namespace std;

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

class OutParser {
private:
	FILE *fout;
	char *buff;
	int sp;
	void write_ch(char ch) {
		if(sp == 65536) {
			fwrite(buff, 1, 65536, fout);
			sp = 0;
			buff[sp++] = ch;
		} else {
			buff[sp++] = ch;
		}
	}
public:
	OutParser(const char* name) {
		fout = fopen(name, "w");
		buff = new char[65536]();
		sp = 0;
	}
	~OutParser() {
		fwrite(buff, 1, sp, fout);
		fclose(fout);
	}
	OutParser& operator << (int n) {
		if(n <= 9) {
			write_ch(n + '0');
		} else {
			(*this) << (n / 10);
			write_ch(n % 10 + '0');
		}
		return *this;
	}
	OutParser& operator << (char ch) {
		write_ch(ch);
		return *this;
	}
};

InParser fin("rmq.in");
OutParser fout("rmq.out");

const int kN = 1e5;
const int kM = 1e6;

int n, root, v[kN], st[kN], p[kN], ans[kM], anc[kN], up[kN], sz[kN];
vector<int> adj[kN];
vector<pair<int, int>> qs[kN];

void buidTree() {
	int head = -1;
	for(int i = 0; i < n; i++) {
		int last = -1;
		p[i] = -1;
		while(head >= 0 && v[st[head]] >= v[i]) {
			last = st[head];
			head--;
		}
		if(head >= 0) {
			p[i] = st[head];
		}
		if(last >= 0) {
			p[last] = i;
		}
		head++;
		st[head] = i;
	}
	for(int i = 0; i < n; i++) {
		if(p[i] != -1) {
			adj[p[i]].emplace_back(i);
		} else {
			root = i;
		}
	}
}

void makeSet(int u) {
	up[u] = u;
	sz[u] = 1;
}

int findRoot(int u) {
	if(u == up[u]) {
		return u;
	}
	return up[u] = findRoot(up[u]);
}

bool unite(int u, int v) {
	u = findRoot(u);
	v = findRoot(v);
	if(u == v) {
		return false;
	}
	if(sz[u] > sz[v]) {
		swap(u, v);
	}
	up[u] = v;
	sz[v] += sz[u];
	return true;
}

void dfs(int u = root) {
	makeSet(u);
	anc[u] = u;
	for(const auto &it: adj[u]) {
		dfs(it);
		unite(u, it);
		anc[findRoot(it)] = u;
	}
	for(const auto &it: qs[u]) {
		int lca = anc[findRoot(it.first)];
		ans[it.second] = v[lca];
	}
}

int main() {
	int m;
	fin >> n >> m;
	for(int i = 0; i < n; i++) {
		fin >> v[i];
	}
	buidTree();
	for(int i = 0; i < m; i++) {
		int l, r;
		fin >> l >> r;
		l--; r--;
		qs[l].emplace_back(r, i);
		qs[r].emplace_back(l, i);
	}
	dfs();
	for(int i = 0; i < m; i++) {
		fout << ans[i] << '\n';
	}
	return 0;
}