#include <iostream>
#include<fstream>
using namespace std;
int d[50][100003],i,j,k,n,v[100003],nr,m,x,y,poz,e,l;
inline int log(int a)
{
    int o=0;while((1<<o)<=a)++o;
    return o-1;
}
inline int minim(int a,int b)
{
    if(a<b)return a;
    return b;
}
int main()
{
    ifstream f("rmq.in");
    f>>n>>nr;for(i=1;i<=n;++i){f>>v[i];d[0][i]=v[i];}
    m=log(n)+1;v[n+1]=9000000;d[0][n+1]=v[n+1];
    for(i=1;i<m;++i)
    {
        cout<<i<<"   ";
        for(j=1;j<n;++j)
        {
            d[i][j]=minim(d[i-1][j],d[i-1][j+(1<<(i-1))]);
            cout<<d[i][j]<<" ";
        }
        cout<<'\n';
    }
    ofstream g("rmq.out");
    for(j=0;j<nr;++j)
    {
        f>>x>>y;
        k=log(y-x);
        e=1<<k;
        poz=minim(d[k][x],d[k][y-e+1]);
        g<<poz<<'\n';
    }
    f.close();
    g.close();
    return 0;
}