#include <fstream>
#include <cmath>
#define NM 100005

using namespace std;

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

int n, m, k, A[NM], M[NM][20];

void Preprocesare()
{
    int i, j, loc;

    for (i=1; i<=n; i++)
    {
        M[i][0]=i;
    }
    loc=1;
    for (i=1; i<=k; i++)
    {
        for (j=1; j<=n; j++)
        {
            if (A[M[j][i-1]]<A[M[j+loc][i-1]])
                M[j][i]=M[j][i-1];
            else
                M[j][i]=M[j+loc][i-1];
        }
        loc *= 2;
    }
}

void RMQ()
{
    int i, x, y, d;
    for (i=1; i<=m; i++)
    {
        fin>>x>>y;
        d=(log(y-x+1)/log(2));
        if (A[M[x][d]]>A[M[y-(int)pow(2, d)][d]])
            fout<<A[M[y-d][d]]<<'\n';
        else
            fout<<A[M[x][d]]<<'\n';
    }
}

int main()
{
    int i, j;
    fin>>n>>m;
    for (i=1; i<=n; i++)
    {
        fin>>A[i];
    }
    k=log(n)/log(2);
    Preprocesare();
    RMQ();
    for (i=1; i<=n; i++)
    {
        for (j=0; j<=k+1; j++)
            fout<<M[i][j]<<" ";
        fout<<'\n';
    }
    return 0;
}