#include <bits/stdc++.h>
using namespace std;
ifstream fin ("rmq.in");
ofstream fout ("rmq.out");
int mt[100005][20];
int v[100005];
int N, M;
int main ()
{
    fin >> N >> M;
    for (int i = 1; i <= N; i++)
        fin >> v[i];
    for (int i = 1; i <= N; i++)
        mt[i][1] = i;
    for (int k = 1, p = 1; p <= N; k++, p *= 2)
        for (int i = 1; i + k <= N; i++)
            mt[i][k + 1] = (v[mt[i][k]] < v[mt[i + k][k]]) ? mt[i][k] : mt[i + k][k];
    for (int i = 1; i <= N; i++, cout << endl)
        for (int j = 1; j <= N; j++)
            cout << mt[i][j] << " ";

    for (int i = 1; i <= M; i++)
    {
        int a, b;
        fin >> a >> b;
        int p = 1;
        int j = 1;
        while (p * 2 <= b - a)
            p *= 2, j++;
        fout << min (v[mt[a][j]], v[mt[b - p + 1][j]]) << "\n";
    }
}