You are given sequence *a*<sub class="lower-index">1</sub>, *a*<sub class="lower-index">2</sub>, ..., *a*<sub class="lower-index">*n*</sub> and *m* queries *l*<sub class="lower-index">*j*</sub>, *r*<sub class="lower-index">*j*</sub> (1 ≤ *l*<sub class="lower-index">*j*</sub> ≤ *r*<sub class="lower-index">*j*</sub> ≤ *n*). For each query you need to print the minimum distance between such pair of elements *a*<sub class="lower-index">*x*</sub> and *a*<sub class="lower-index">*y*</sub> (*x* ≠ *y*), that:
 -  both indexes of the elements lie within range [*l*<sub class="lower-index">*j*</sub>, *r*<sub class="lower-index">*j*</sub>], that is, *l*<sub class="lower-index">*j*</sub> ≤ *x*, *y* ≤ *r*<sub class="lower-index">*j*</sub>; -  the values of the elements are equal, that is *a*<sub class="lower-index">*x*</sub> = *a*<sub class="lower-index">*y*</sub>. 
The text above understands distance as |*x* - *y*|.
The first line of the input contains a pair of integers *n*, *m* (1 ≤ *n*, *m* ≤ 5·10<sup class="upper-index">5</sup>) — the length of the sequence and the number of queries, correspondingly. 

The second line contains the sequence of integers *a*<sub class="lower-index">1</sub>, *a*<sub class="lower-index">2</sub>, ..., *a*<sub class="lower-index">*n*</sub> ( - 10<sup class="upper-index">9</sup> ≤ *a*<sub class="lower-index">*i*</sub> ≤ 10<sup class="upper-index">9</sup>). 

Next *m* lines contain the queries, one per line. Each query is given by a pair of numbers *l*<sub class="lower-index">*j*</sub>, *r*<sub class="lower-index">*j*</sub> (1 ≤ *l*<sub class="lower-index">*j*</sub> ≤ *r*<sub class="lower-index">*j*</sub> ≤ *n*) — the indexes of the query range limits.
from sys import stdin
input=stdin.readline
from math import ceil, log2
M=10**10
def u(p, value,n):                               #updating values
    tree[p + n]=value;  
    p = p+n;
    i = p
    while i > 1 : 
        tree[i >> 1] = min(tree[i] , tree[i ^ 1]);  
        i >>= 1;
def minseg( st, ss, se, qs, qe, index) : # 0 based indexing
    if (qs <= ss and qe >= se) : 
        return st[index]  
    if (se < qs or ss > qe) : 
        return M
    mid = ss + (se - ss) // 2
    return min(minseg(st, ss, mid, qs, qe, (2 * index) ), minseg(st, mid + 1, se, qs, qe, (2 * index) + 1));         
n,m=map(int, input().split())
a=list(map(int, input().split()))
c=[]
for i in range(m):
    l,r=map(int, input().split())
    c.append([l,r,i])
c.sort()    
tree=[0]*(2**((int)(ceil(log2(n)))+1))
temp=[M]*((2**((int)(ceil(log2(n)))))-n)
a+=temp
N=len(a)
d={}
prv,nxt=[],[-1]*n
ans=[-1]*m
for i in range(n):
    if a[i] in d: prv.append(i-d[a[i]])
    else:               prv.append(M)
    d[a[i]]=i
d.clear()
for i in range(n-1,-1,-1):
    if a[i] in d: nxt[i]=d[a[i]]
    d[a[i]]=i
prv+=temp
for i in range(N) :  
    tree[N + i] = prv[i]
for i in range(N - 1, 0, -1) :  
    tree[i] = min(tree[i << 1] , tree[i << 1 | 1]);
j=0
#print(tree,'\n',a,'\n',prv,'\n',nxt)
for i in range(m):
    while(j<c[i][0]-1): 
        if nxt[j]==-1: 
            j+=1
            continue
        u(nxt[j],M,N)
        j+=1  
    ans[c[i][2]]=minseg(tree,0,N-1,c[i][0]-1,c[i][1]-1,1)    
    if ans[c[i][2]]==M:
        ans[c[i][2]]=-1
for i in ans: print(i)        
    