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.
__author__ = 'ruckus'

'''def compare(a1):
    return a1[2]
'''
def rangeMap(a):
    rast = [0 for i in range(len(a))]
    for i in range(len(a)):
        if a[i] != 0.1:
            Save = a[i]
            Pos = []
            Pos.append(i)
            a[i] = 0.1
            while Save in a:
                Pos.append(a.index(Save))
                a[a.index(Save)] = 0.1
            if len(Pos) == 1:
                rast[i] = 10e20
            else:
                rast[i] = Pos[1] - Pos[0]
                for j in range(1, len(Pos)-1):
                    rast[Pos[j]] = min(Pos[j]-Pos[j-1], Pos[j+1]-Pos[j])
                rast[Pos[len(Pos)-1]] = Pos[len(Pos)-1] - Pos[len(Pos)-2]
    return rast

n, m = input().split()

a = input().split()
for i in range(len(a)):
    a[i] = int(a[i])
for i in range(int(m)):
    req = input().split()
    req[0] = int(req[0])
    req[1] = int(req[1])
    rast = rangeMap(a[req[0]-1:req[1]])
    Min = min(rast)
    if Min == 10e20:
        Min = -1
    print(Min)
'''Saved = []
fl = 0
for i in range(int(m)):
    req = input().split()
    req[0] = int(req[0])
    req[1] = int(req[1])
    for S in Saved:
        if S[0] >= req[0]-1 and S[1] <= req[1]-1:
            print(S[2])
            fl = 1
            break
    if fl == 0:
        j = a[req[0]-1:req[1]]
        minimum = 500000
        for k in range(len(j)):
            for l in range(k+1, len(j)):
                if l-k > minimum:
                    break
                if j[k] == j[l]:
                    if l-k < minimum:
                        minimum = l-k
                        Saved.append([k+req[0]-1, l+req[0]-1, minimum])
                    break
            if minimum == 1:
                break
        Saved.sort(key=compare)
        if minimum == 500000:
            minimum = -1
        print(minimum)
    else:
        fl = 0
        continue'''