#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;
}