#include<cstdio>
#include<algorithm>
#define MAXN 100000
using namespace std;
struct mycreation{
    int x, y, z;
};
mycreation a[MAXN+1];
int ans[MAXN+1],v[MAXN+1],po[MAXN+1],r[MAXN+1];
int aint[4*MAXN],l[MAXN+1],poz,maxim,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(maxim<aint[p])
            maxim=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(){
    freopen("pq.in","r",stdin);
    freopen("pq.out","w",stdout);
    int n,q,i,p;
    scanf("%d%d",&n,&q);
    for(i=1;i<=n;i++){
        scanf("%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++){
        scanf("%d%d",&a[i].x,&a[i].y);
        a[i].z=i;
    }
    sort(a+1,a+q+1,cmp);
    p=1;
    for(i=1;i<=n;i++){
        while((p<=q)&&(a[p].x==i)){
            maxim=-1;
            right=a[p].y;
            query(1,1,n);
            ans[a[p].z]=maxim;
            p++;
        }
        if(r[i]){
            poz=r[i];
            l[poz]=-1;
            update(1,1,n);
        }
    }
    for(i=1;i<=q;i++)
        printf("%d\n",ans[i]);
    return 0;
}