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.
from array import *

def gp2(n):
    x = 2
    while x < n:
        x += x
    return x

IntMaxVal = 1000000000 + 7
    
class MinTree:
    def __init__(self, n):
        self.n = gp2(n)
        self.data = [ IntMaxVal for ix in range(0, 2 * self.n) ]
		
    def set(self, i, item):
        i += self.n
        self.data[i] = item
        i //= 2;
        while i > 0:
            self.data[i] = min(self.data[2*i], self.data[2*i + 1])
            i //= 2
	
    def getValue(self, l, r, i, fullL, fullR):
        if l == fullL and r + 1 == fullR:
            return self.data[i]
        else:
            m = (fullL + fullR) // 2
            if l < m and r >= m:
                return min(self.getValue(l, m - 1, 2 * i, fullL, m),
												self.getValue(m, r, 2 * i + 1, m, fullR));
            elif l < m: return self.getValue(l, r, 2 * i, fullL, m)
            else: return self.getValue(l, r, 2 * i + 1, m, fullR)
	
    def getValue2(self, l, r):
        return self.getValue(l, r, 1, 0 , self.n)

n, q = [int(x) for x in input().split()]
v = [int(x) for x in input().split()]
queries = [ (int(a[0]) - 1, int(a[1]) - 1, ix) for a, ix in [(input().split(), ix) for ix in range(0, q)] ]
queries.sort()
	
tree = MinTree(n)
ptr = n - 1
closest_right = dict()
for i in range(q - 1, -1, -1):
    while ptr >= queries[i][0]:
        x = v[ptr]
        if x in closest_right:
            i2 = closest_right[x]
            tree.set(i2, i2 - ptr)
        closest_right[x] = ptr
        ptr = ptr - 1
    
    ans = tree.getValue2(queries[i][0] , queries[i][1])
    if ans == IntMaxVal: ans = -1
    queries[i] = ( queries[i][2] , ans)

queries.sort()
print(' '.join([ str(q[1]) for q in queries]))
	
	# for (auto &q : queries) cout << get<3>(q) << endl;
# }