#include <cstdio>
#include <algorithm>
#define MAXN 100000
struct mycreation{
    int x, y, z;
}a[MAXN+1];
int ans[MAXN+1], v[MAXN+1], po[MAXN+1], r[MAXN+1];
int aint[4*MAXN], l[MAXN+1], poz, max, right;
bool cmp(const mycreation a, const mycreation b){
    return a.x<b.x;
}
void query(int p, int st, int dr){
    if(dr<=right){
        if(max<aint[p]){
            max=aint[p];
        }
    }else{
        int m=(st+dr)/2;
        query(2*p, st, m);
        if(m<right){
            query(2*p+1, m+1, dr);
        }
    }
}
void update(int p, int st, int dr){
    if(st==dr){
        aint[p]=l[st];
    }else{
        int m=(st+dr)/2;
        if(poz<=m){
            update(2*p, st, m);
        }else{
            update(2*p+1, m+1, dr);
        }
        if(aint[2*p]>aint[2*p+1]){
            aint[p]=aint[2*p];
        }else{
            aint[p]=aint[2*p+1];
        }
    }
}
void dfs(int p, int st, int dr){
    if(st==dr){
        aint[p]=l[st];
    }else{
        int m=(st+dr)/2;
        dfs(2*p, st, m);
        dfs(2*p+1, m+1, dr);
        if(aint[2*p]>aint[2*p+1]){
            aint[p]=aint[2*p];
        }else{
            aint[p]=aint[2*p+1];
        }
    }
}
int main(){
    int n, q, i, p;
    FILE *fin, *fout;
    fin=fopen("pq.in", "r");
    fout=fopen("pq.out", "w");
    fscanf(fin, "%d%d", &n, &q);
    for(i=1; i<=n; i++){
        fscanf(fin, "%d", &v[i]);
        if(po[v[i]]!=0) l[i]=i-po[v[i]], r[po[v[i]]]=i;
        else l[i]=-1;
        po[v[i]]=i;
    }
    dfs(1, 1, n);
    for(i=1; i<=q; i++){
        fscanf(fin, "%d%d", &a[i].x, &a[i].y);
        a[i].z=i;
    }
    std::sort(a+1, a+q+1, cmp);
    p=1;
    for(i=1; i<=n; i++){
        while((p<=q)&&(a[p].x==i)){
            max=-1;
            right=a[p].y;
            query(1, 1, n);
            ans[a[p].z]=max;
            p++;
        }
        if(r[i]){
            poz=r[i];
            l[poz]=-1;
            update(1, 1, n);
        }
    }
    for(i=1; i<=q; i++){
        fprintf(fout, "%d\n", ans[i]);
    }
    fclose(fin);
    fclose(fout);
    return 0;
}