const int N=3e5+5;
 
    int n,m,_;
    int i,j,k;
    int a[N];
    struct Node
    {
        int l,r;
        int sz;
        int minn;
        void update(int x){ sz++; minn=x; }
    }t[N<<5];
    int root[N],tot=0;

void push_up(int id)
{
    t[id].minn=min(t[t[id].l].minn,t[t[id].r].minn);
}

void update(int &x,int y,int val,int pos,int l,int r)
{
    x=++tot;
    t[x]=t[y];
    t[x].update(pos);
    if(l==r) return ;
    else{
        int mid=l+r>>1;
        if(mid>=val) update(t[x].l,t[y].l,val,pos,l,mid);
        else update(t[x].r,t[y].r,val,pos,mid+1,r);
        push_up(x);
    }
}

int query(int id,int l,int r,int pos)
{
    if(l==r) return l;
    else{
        int mid=l+r>>1;
        if(t[t[id].l].minn<pos) return query(t[id].l,l,mid,pos);
        else return query(t[id].r,mid+1,r,pos); 
    }
}

int main()
{
    //IOS;
    while(~sdd(n,m)){
        forn(i,1,n){
            sd(a[i]);
            update(root[i],root[i-1],a[i],i,0,n);
        }
        while(m--){
            int l,r;
            sdd(l,r);
            int ans=query(root[r],0,n,l);
            pd(ans);
        }
    }
    //PAUSE;
    return 0;
}