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 collections import defaultdict
n, m = map(int, input().split())
*nums, = map(int, input().split())
class SegmentTree():
    def __init__(self):
        self.maxn = 10**18
        self.st = defaultdict(lambda : self.maxn)
        
    def update(self, o, l, r, idx, val):
        if idx < l or idx > r:
            return 
        if l == r:
            if val < self.st[o]:
                self.st[o] = val 
            return 
        
        mid = (l + r) // 2
        self.update(o << 1, l, mid, idx, val)
        self.update(o << 1 | 1, mid + 1, r, idx, val)
        self.st[o] = min(self.st[o << 1], self.st[o << 1 | 1])

    def query(self, o, l, r, L, R):
        if L <= l and r <= R:
            return self.st[o]
        if l > R or r < L:
            return self.maxn
        mid = (l + r) // 2
        
        return min(self.query(o << 1, l, mid, L, R), self.query(o << 1 | 1, mid + 1, r, L, R))

st = SegmentTree()
hm = dict()
n = len(nums)
q = []
for i in range(m):
    x, y = map(int, input().split())
    q.append([x,y,i])
q.sort(key = lambda x : x[1]) 
res = [-1] * m
idx = 0
for i in range(m):
    while idx <= q[i][1] - 1:
        if nums[idx] in hm:
            st.update(1,1,n,hm[nums[idx]],idx + 1 - hm[nums[idx]])
        hm[nums[idx]] = idx + 1
        idx += 1
    tmp = st.query(1,1,n,q[i][0],q[i][1])
    if tmp != st.maxn:
        res[q[i][-1]] = tmp

for i in range(m):
    print(res[i])
