#include <stdio.h>
#include <stdlib.h>
#define MAX 100002
#define LOGMAX 18
#define in "rmq.in"
#define out "rmq.out"

int a[MAX], M[LOGMAX][MAX], n, lg[MAX];

void process_matrix()
{
	unsigned int i,j;
	
	for (j = 1 ; 1 << j <= n; j++)
		for (i = 1; i + (1 <<(j-1)) < n; i++)
		{
			//printf("i %d i+ 1 << j-1 %d\n", i, i + (1<<(j-1)));
			if (a[M[j-1][i]] <= a[M[j-1][i + (1<<(j - 1))]])
				M[j][i] = M[j-1][i];
			else
				M[j][i] = M[j-1][i + (1<<(j-1))];
		}
	printf("OUt\n");
}

int minim(int x , int y)
{
	int k, m;
	k = lg[y-x+1];
	//printf("k %d %d %d\n", k,  x, y);
	if (y == x - 1 + (1 << k))
		return M[k][x];
	m = minim(x + (1 << k), y);
	return a[M[k][x]] <= a[m] ? M[k][x] : m;
}

int main()
{
	unsigned int i, z, m, x, y,j, k;
	FILE *fin, *fout;
	
	if ((fin = fopen(in, "r")) == NULL)
	{
		printf("Eroare \n");
		exit(-1);
	}
	//read dimension of vectors
	fscanf(fin, "%d%d", &n, &m);

	//read the vectors
	for (i = 1; i<=n ; i++)
	{
		fscanf(fin, "%d", &a[i]);		
		M[0][i] = i;
	}
	for (i = 2; i<=n ; i++)
	{
		lg[i] = lg[i/2] + 1;
	}	
	process_matrix();
	/*
	for (i = 1; i <= n; i++)
	{
		for (j = 0; 1 << j <= n; j++)
			printf("%d ", M[i][j]);
		printf("\n");
	}
	printf("\n");
	*/
	fout = fopen(out, "w");
	
	for (i = 0; i < m; i++)
	{
		fscanf(fin, "%d%d", &x, &y);

		//printf("x %d y %d z %d x+ 1 <<z %d M[x][z] %d M[x+1..][z-1] %d\n", x, y, z, x + (1<<z), M[x][z], M[x + (1<<z)][z-1]);
		j = lg[y - x + 1];
		k = y + 1 - (1 << j);
		//printf("j %d a %d b %d k %d M[j][x] %d M[j][k] %d\n", j, x, y, k, M[j][x], M[j][k]);
		//z = minim(x, y);
		if (a[M[j][x]] <= a[M[j][k]])
		{
			z = M[j][x];
		}
		else
		{
			z = M[j][k];
		}
		//printf("k = %d  z = %d\n", k, z);
		fprintf(fout, "%d\n", a[z]);
	}
	fclose(fin);
	fclose(fout);
	return 0;
}