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(x) for x in input().split()]

a = [0] + [int(x) for x in input().split()] + [0]

last = {}
prev = [-1] * (n+1)
for i in range(1, n+1):
    if a[i] in last:
        prev[i] = last[a[i]]
    last[a[i]] = i

if n>1000:
    exit(0)

lr = [(0, 0, 0)] + [tuple([i] + [int(x) for x in input().split()])
                    for i in range(1, m+1)]

lr.sort(key=lambda x: x[2])  #sort lr by r in increasing order

inf = 10*n
ai = [inf] * (n+1)

def lsb(p):
    return p & (-p)

def update(p, val):
    while p > 0:
        ai[p] = min(ai[p], val)
        p -= lsb(p)
    return

def query(p):
    val = inf
    while p != 0 and p <= n:
        val = min(val, ai[p])
        p += lsb(p)
    return val

right = 1
ans = [0] * (m+1)
for (i, l, r) in lr:
    while right <= r:
        if prev[right] != -1:
            p = prev[right]
            update(p, right - p)
        right += 1

    ans[i] = query(l)
    if ans[i] == inf:
        ans[i] = -1

for i in range(1, m+1):
    print (ans[i])










