#include <bits/stdc++.h>

#define nmax 100000

using namespace std;

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.pos < p2.pos;
}

int aint[nmax+1];

int lv[nmax];


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()
{
    ios::sync_with_stdio(false); cin.tie(0);

    cin >> n >> q;

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

    for(i=1;i<=q;++i)
    {
        cin >> 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;
                }
            }

        cout << Query( n-ss.l) << "\n";

    }

    return 0;
}