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.
inp = input().split(' ')
n, m = int(inp[0]), int(inp[1])
numbers = {}
inp = input().split(' ')
for i in range(n):
    a = int(inp[i])
    if numbers.get(a) == None:
        numbers[a] = [i]
    else:
        numbers[a].append(i)
print(numbers)
dists = {}
for a in numbers.keys():
    ind  = numbers[a]
    for i in range(len(ind) - 1):
        dists[ind[i]] = ind[i + 1] - ind[i]
queries = [input() for i in range(m)]
for qr in queries:
    beg = int(qr.split(' ')[0]) 
    end = int(qr.split(' ')[1])
    curmin = -1
    for i in range(beg - 1, end):
        if dists.get(i, None) != None and i + dists[i] < end:
            if curmin == -1 or curmin > dists[i]:
                curmin = dists[i]
        if (curmin == 1):
            break
    ans = curmin <= (end - beg) and curmin or -1
    print(ans)