#include <iostream>
#include <fstream>
#include <stack>
#include <algorithm>
#include <string>
#include <queue>
#include <vector>
#include <map>
#include <cmath>

using namespace std;

ifstream fin("a.in");
ofstream fout("a.out");                                    //maybe change log

int min(int a, int b) { return (a < b ? a : b); }

int** preProcess(int* input, int n) {
	int** sparse = new int* [n];

	for (int i = 0; i < n; ++i)
		sparse[i] = new int[17];

	for (int i = 0; i < n; ++i)
		sparse[i][0] = i;

	for (int j = 1; pow(2, j) <= n; ++j) {
		for (int i = 1; i + pow(2, j) - 1 < n; ++i) {
			if (input[sparse[i][j - 1]] < input[sparse[i + (int)pow(2, j - 1)][j - 1]])
				sparse[i][j] = sparse[i][j - 1];
			else
				sparse[i][j] = sparse[i + (int)pow(2, j - 1)][j - 1];
		}
	}

	return sparse;
}

int rmq(int st, int dp, int** sparse, int* input) {
	int l = dp - st + 1;
	int k = log(l);

	return min(input[sparse[st][k]], input[sparse[st + l - (int)pow(2, k)][k]]);
}

int main() {
	int n, m;
	fin >> n >> m;

	int v[100004];

	for (int i = 0; i < n; ++i)
		fin >> v[i];

	int** sparse = preProcess(v, n);

	int x, y;
	for (int i = 0; i < m; ++i) {
		fin >> x >> y;
		fout << rmq(x, y, sparse, v);
	}

	return 0;
}