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 = map(int, input().split())
arr = list(map(int, input().split()))
class Node:
    def __init__(self, i, j):
        self.l = i
        self.r = j
        self.val = float("inf")
        self.lazy = float("inf")
        if i + 1 == j:
            return 
        mid = (i + j) // 2
        self.left = Node(i, mid)
        self.right = Node(mid, j)
    
    def update(self, i, j, val):
        if self.l == i and self.r == j:
            self.val = min(self.val, val)
            self.lazy = min(self.lazy, val)
            return
        mid = (self.l + self.r) // 2
        if i >= mid:
            self.right.update(i, j, val)
        elif j <= mid:
            self.left.update(i, j, val)
        else:
            self.left.update(i, mid, val)
            self.right.update(mid, j, val)
        self.val = min(self.left.val, self.right.val)
        
    def find(self, i):
        if self.l + 1 == self.r:
            self.val = min(self.val, self.lazy)
            return self.val
        if self.lazy < float("inf"):
            self.left.lazy = min(self.left.lazy, self.lazy)
            self.right.lazy = min(self.right.lazy, self.lazy)
        mid = (self.l + self.r) // 2
        if i < mid:
            return self.left.find(i)
        else:
            return self.right.find(i)
            
        
s = []
for _ in range(m):
    l, r = map(int, input().split())
    s.append([r, l - 1, _])
    
s.sort()
res = [-1 for i in range(m)]

j = 0
d = {}
node = Node(0, n)
for i, n in enumerate(arr):
    if n in d:
        node.update(0, d[n] + 1, i - d[n])
    while j < m and s[j][0] == i + 1:
        res[s[j][2]] = node.find(s[j][1])
        j += 1
    d[n] = i

for i in res:
    if i == float("inf"):
        print(-1)
    else:
        print(i)