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.
def find1(X, l, r):
    m = len(X)
    if r < X[0]:
        return float('inf')
    if X[-1] < l:
        return float('inf')
    if l <= X[0]:
        left_point = 0
    else:
        s = 0
        e = m-1
        while s+1 < e:
            mid = (s+e)//2
            if X[mid] > l:
                s, e = mid, e
            else:
                s, e = s, mid
        left_point = e
    if X[-1] <= r:
        right_point = m-1
    else:
        s = 0
        e = m-1
        while s+1 < e:
            mid = (s+e)//2
            if X[mid] <= r:
                s, e = mid, e
            else:
                s, e = s, mid
        right_point = s
    if left_point==right_point:
        return float('inf')
    return X[right_point]-X[left_point]

def process(A, Q):
    d = {}
    n = len(A)
    answer = []
    for i in range(n):
        x = A[i]
        if x not in d:
            d[x] = []
        d[x].append(i)
    for l, r in Q:
        my_min = float('inf')
        for x in d:
            my_min = min(my_min, find1(d[x], l-1, r-1))
        if my_min==float('inf'):
            answer.append(-1)
        else:
            answer.append(my_min)
    return answer

n, m = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
Q = []
for i in range(m):
    l, r = [int(x) for x in input().split()]
    Q.append([l, r])
answer = process(A, Q)
for x in answer:
    print(x)            