#include <iostream>
#include <fstream>
#include <vector>
#define N 100001

using namespace std;

ifstream fin("rmq.in");
ofstream fout("rmq.out");

int v[18][100001];
int n, m, x;

int logs[N];

void compute_logs() {
	logs[2] = 1;
	for (int i = 3; i < N; ++i) {
		logs[i] = logs[i - 1];
		if ((i & (i - 1)) == 0) {
			logs[i]++;
		}
	}
}

int min(int a, int b) {
	if (a == 0) return a;
	if (b == 0) return b;
	if (a < b) {
		return a;
	} else {
		return b;
	}
}

int main() {
	fin >> n >> m;
	for (int i = 1; i <= n; ++i) {
		fin >> v[0][i];
	}
	compute_logs();

	int k = 1;
	for (int i = 1; k <= n; ++i) {
		for (int j = 1; j <= n - k; ++j) {
			v[i][j] = min(v[i - 1][j], v[i - 1][j + k]);
		}
		k = k * 2;
	}

	k = 1;


	for (int i = 1; k <= n; ++i) {
		for (int j = 1; j <= n - k; ++j) {
			cout << v[i][j] << ' ';
		}
		k = k * 2;
		cout <<'\n';
	}

	int p, q;
	for (int i = 0; i < m; ++i) {
		fin >> p >> q;
		int ldif = logs[q - p];
		fout << min(v[ldif][p], v[ldif][q - ldif]) << '\n';
	}
	return 0;
}