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.
n,m=(int(i) for i in input().split())
a=[int(i) for i in input().split()]
##a_={i: a[i] for i in range(len(a))}
otvet=''
def func(a):
    l,r=(int(i) for i in input().split())
    a=a[l-1:r]
    toreturn=[]
    ret=[]
    flag=False
    for i in range(len(a)):
        if i>len(a) or a[i]==None:
            break
        else:
            if a.count(a[i])>1:
                ind=[i]
                k=a[i]
                a[i]=None
                flag=True
                for j in range(len(a)-i-1):
                    if a[j+i+1]==k:
                        ind.append(j+i+1)
                        a[j+i+1]=None
                for j in range(len(ind)-1):
                    ret.append(ind[j+1]-ind[j])
                toreturn.append(min(ret))
                ret=[]
    if not flag:
        return '-1'
    else:
        return str(min(toreturn))



for i in range(m):
    otvet+=func(a.copy())+'\n'
print(otvet)
