#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
using namespace std;
ifstream fin("saracsaurege.in");
ofstream fout("saracsaurege.out");
int n,q,rmq[2][50010],v[50010],i,a[50010],l,x,y,m;
inline void run(int N)
{
    int l,r,i,lg,LG;
    for(i=1;i<=n;i++)
        rmq[0][i]=v[i];
    for(lg=1,LG=2,m=1;LG<=N;LG<<=1,lg<<=1,m=1-m)
        for(l=1,r=LG;r<=N;l++,r++)
            rmq[m][l]=max(rmq[m-1][l],rmq[m-1][l+lg]);
}
int main()
{
    fin>>n>>q;
    for(i=2;i<=n;i<<=1)
        a[i]=1;
    for(i=1;i<=n;i++)
        a[i]+=a[i-1];
    for(i=1;i<=n;i++)
        fin>>v[i];
    l=1<<30;
    for(;q;q--)
    {
        fin>>x>>y;
        if(y-x+1<l)
        {
            l=a[y-x+1];
            run(l+1);
        }
        fout<<max(rmq[1-m][x],rmq[1-m][y-(1<<l)+1])<<'\n';
    }
    return 0;
}