#include <stdio.h>

const int oo = 1<<30;

int a[100000], ms[1000];

int min(int a, int b) {
	if (a > b)
		return b;
	return a;
}

int max(int a, int b) {
	if (a > b)
		return a;
	return b;
}

int main(int argc, char *argv[]) {
	int n, m, i, j, l, u, mn, c, ls, ld;

	FILE *fi = fopen("rmq.in", "r");	
	fscanf(fi, "%d %d", &n, &m);
	for (i = 0; i < n; ++i)
		fscanf(fi, "%d", a+i);

	for (mn = 0; mn*mn < n; ++mn)
		;
	--mn;

	for (i = 0; i*mn < n; ++i) {
		ms[i] = oo;
		for (j = i*mn; (j < (i+1)*mn) && (j < n); ++j)
			ms[i] = min(ms[i], a[j]);
	}
	
	for (i = 0; i < n; ++i)
		printf("%d ", a[i]);
	printf("\n");

	for (i = 0; i*mn < n; ++i)
		printf("%d ", ms[i]);
	printf("\n"); 

	FILE *fo = fopen("rmq.out", "w");
	while (m--) {
		fscanf(fi, "%d %d", &l, &u);
		--l, --u;

		printf("%d..%d: ", l, u);
		c = oo;
		for (i = 0; i*mn < l; ++i)
			;
		ls = min(i*mn, u);
		++i;
		for (; i*mn <= u; ++i) {
			c = min(c, ms[i]);
			printf("%d ", ms[i]);
		}
		ld = max((i-1)*mn, l);

		printf("| ");
		for (j = l; j <= ls; ++j) {
			c = min(c, a[j]);
			printf("%d ", a[j]);
		}
		printf("| ");
		for (j = ld; j <= u; ++j) {
			c = min(c, a[j]);
			printf("%d ", a[j]);
		}
		printf("\n");

		fprintf(fo, "%d\n", c);
			
	}
	fclose(fo);
	fclose(fi);

	return 0;
}