#include <bits/stdc++.h>

#define nmax 100000

using namespace std;
ifstream fin("pq.in");
ofstream fout("pq.out");

int lastviz[nmax];

vector<int>A;
int n,q;


struct ir{
    int l,r;
    int pos;

public:
    ir(int ml,int mr,int mpos): l(ml), r(mr), pos(mpos){}

};

vector<ir>Q;

bool cmp(const ir& p1 ,const ir& p2)
{
    return p1.r < p2.r;
}

int aint[nmax+1];

int lv[nmax];

int answer[nmax+1];

int lsb(int x)
{
    return x & -x;
}

void Update(int pos,int val)
{
    while(pos<=n)
    {
        aint[pos] = max(aint[pos],val);
        pos += lsb(pos);
    }
}


int Query(int pos)
{
    int maxi = -1;

    while( pos)
    {
        maxi = max(maxi,aint[pos] );
        pos -= lsb(pos);
    }
    return maxi;
}

int32_t main()
{

    fin >> n >> q;

    int i;
    int x,y;
    for(i =1 ;i<=n;++i)
    {
        fin >> x;
        A.push_back(x);
        aint[i] = -1;
    }

    for(i=1;i<=q;++i)
    {
        fin >> x >> y;


        Q.push_back( ir(x,y,i)  );
    }
    sort(Q.begin(),Q.end(),cmp);


    int last=0;


    for(auto ss : Q)
    {
        if( ss.r > last)
            {
                while(last < ss.r)
                {
                    ++last;
                    if(lv[ A[last-1]] != 0)
                    {

                        Update(n-lv[A[last-1]], last - lv[A[last-1]] );

                    }

                    lv[A[last-1] ] = last;
                }
            }

        answer[ss.pos] = Query( n-ss.l);
    }

    for(i=1;i<=q;++i)
        fout << answer[i] << "\n";
    return 0;
}