#include <bits/stdc++.h>
using namespace std;

const int nmax = 100005;
int H[4*nmax];
int v[nmax], prv[nmax], nxt[nmax], last[nmax], sol[nmax];
int n, q, a, b;


vector <pair <pair <int, int>, int>> Q;

void update(int node, int lo, int hi, int pos, int val) {
    if(lo == hi) {
        H[node] = val;
        return;
    }

    int mid = (lo + hi) / 2;

    if(pos <= mid)
        update(2*node, lo, mid, pos, val);
    else
        update(2*node+1, mid+1, hi, pos, val);
    H[node] = max(H[2*node], H[2*node+1]);
}

int query(int node, int lo, int hi, int a, int b) {
    if(a <= lo && hi <= b)
        return H[node];

    int mid = (lo + hi) / 2;
    int ret = 0;

    if(a <= mid)
        ret = max(ret, query(2*node, lo, mid, a, b));
    if(mid < b)
        ret = max(ret, query(2*node+1, mid+1, hi, a, b));
    return ret;
}

int main() {
    ifstream f("pq.in");
    ofstream g("pq.out");

    f>>n>>q;

    for(int i=1; i<=n; i++) {
        f>>v[i];

        if(last[v[i]] == 0)
            prv[i] = i;
        else {
            prv[i] = last[v[i]];
            nxt[last[v[i]]] = i;

            update(1, 1, n, i, i-prv[i]+1);
        }

        last[v[i]] = i;
    }

    /*
    for(int i=1; i<=n; i++)
        cout<<v[i]<<" ";
    cout<<"\n";
    for(int i=1; i<=n; i++)
        cout<<prv[i]<<" ";
    cout<<"\n";
    */



    for(int i=1; i<=q; i++) {
        f>>a>>b;
        Q.push_back(make_pair(make_pair(a, b), i));
    }

    sort(Q.begin(), Q.end());

    int currentQuery = 0;
    for(int i=1; i<=n; i++) {
        while(currentQuery < int(Q.size()) && Q[currentQuery].first.first < i)
            currentQuery++;
        if(currentQuery == int(Q.size()))
            break;

        while(currentQuery < int(Q.size()) && Q[currentQuery].first.first == i) {
            sol[Q[currentQuery].second] = query(1, 1, n, i, Q[currentQuery].first.second);
            //cout<<"am facut un query cu raspunsul "<<query(1, 1, n, i, Q[currentQuery].first.second)<<"\n";
            ++currentQuery;
        }
        if(currentQuery == int(Q.size()))
            break;

        if(nxt[i] > 0) {
            update(1, 1, n, nxt[i], 0);
            //cout<<"pula\n";
        }
    }

    for(int i=1; i<=q; i++)
        g<<sol[i] - 1<<"\n";


    return 0;
}