#include <bits/stdc++.h>
#define nmax 100005
using namespace std;
ifstream in("pq.in");
ofstream out("pq.out");

int sol[nmax], v[nmax], ap[nmax], arb[4*nmax]; 

int pereche[nmax];

vector<pair<int,int> > itv[nmax];

void upd(int poz, int st, int dr, int pz, int val){
    if(st > pz || dr < pz) return;
    if(st == dr){
        arb[poz] = max(val, arb[poz]);
        return;
    }
    int mid = (st+dr)/2;
    upd(poz*2, st, mid, pz, val);
    upd(poz*2+1, mid+1, dr, pz, val);
    arb[poz] = max(arb[poz*2],arb[poz*2+1]);
}

int sum(int poz, int st, int dr, int a, int b){
    if(st > b || dr < a) return 0;
    if(st >= a && dr <= b) return arb[poz];
    int mid = (st+dr)/2;
    int val1 = sum(poz*2, st, mid, a, b);
    int val2 = sum(poz*2+1, mid+1, dr, a, b);
    return max(val1,val2);
}

int main(){
    int n,q;
    in >> n >> q;
    for(int i=1; i<=n; i++){
        in >> v[i];
        if(ap[v[i]]){
            pereche[i] = ap[v[i]];
        }
        ap[v[i]] = i;
    }
    for(int i=0; i<q; i++){
        int a,b;
        in >> a >> b;
        itv[b].push_back({a, i});
    }

    for(int r = 1; r<=n; r++){
        if(pereche[r])
            upd(1, 1, n, pereche[r], r-pereche[r]);
        for(auto elem: itv[r]){
            int l = elem.first;
            int qst = elem.second;
            sol[qst] = sum(1, 1, n, l, r);
            if(sol[qst] == 0){
                sol[qst]--;
            }
        }
    }

    for(int i=0; i<q; i++){
        out << sol[i] << '\n';
    }
    return 0;
}