#include <fstream>
#include <algorithm>
using namespace std;
int v[100005];
int ans[1000005];
int stiva[100005];
struct intr
{
    int l,r,nr;
}intrebare[1000005];
bool cmp(intr x,intr y)
{
    return x.r<y.r;
}
 ifstream cin("rmq.in");
    ofstream cout("rmq.out");
int main()
{
    int n,m,poz=0,pozvec=1;
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        cin>>v[i];
    }
    for(int i=1;i<=m;i++)
    {
        cin>>intrebare[i].l>>intrebare[i].r;
        intrebare[i].nr=i;
    }
    sort(intrebare+1,intrebare+m+1,cmp);
    for(int i=1;i<=n;i++)
    {
        while(poz>0&&v[stiva[poz]]>=v[i])
        {
            poz--;
        }
        poz++;
        stiva[poz]=i;
        while(intrebare[pozvec].r==i)
        {
           int st=1,dr=poz,mij;
           while(st<=dr)
           {
               mij=(st+dr)/2;
               if(stiva[mij]>=intrebare[pozvec].l)
               {
                   ans[intrebare[pozvec].nr]=v[stiva[mij]];
                   dr=mij-1;
               }
               else
               {
                   st=mij+1;
               }
           }
           pozvec++;
        }
    }
    for(int i=1;i<=m;i++)
    {
        cout<<ans[i]<<'\n';
    }
    return 0;
}