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.
import sys
input = sys.stdin.readline

class FenwickTreeMinMax:
    def __init__(self, n, func, ini):
        self.size = n
        self.a = [ini] * (n + 1)
        self.b = self.a[:]
        self.func = func
        self.ini = ini

    def _lowbit(self, index):
        return index & (-index)

    def update(self, index, val):
        self.a[index] = val
        while index <= self.size:
            self.b[index] = val
            i = 1
            while i < self._lowbit(index):
                self.b[index] = self.func(self.b[index], self.b[index - i])
                i <<= 1
            index += self._lowbit(index)

    def query(self, l, r):
        res = self.ini
        while r >= l:
            res = self.func(res, self.a[r])
            r -= 1
            while r - self._lowbit(r) >= l:
                res = self.func(res, self.b[r])
                r -= self._lowbit(r)
        return res


class BinIndexTreeMin:
    def __init__(self, size):
        self.size = size
        self.a = [10 ** 9 for _ in range(size + 5)]
        self.h = self.a[:]
        self.mn = 10 ** 9

    def update(self, x, v):
        if v < self.mn:
            self.mn = v
        a = self.a
        h = self.h
        a[x] = v
        while x <= self.size:
            if h[x] >= v:
                h[x] = v
            else:
                break
            x += self.lowbit(x)

    def query(self, l, r):
        ans = self.a[r]
        while l != r:
            r -= 1
            while r - self.lowbit(r) > l:
                if ans > self.h[r]:
                    ans = self.h[r]
                    if ans == self.mn:
                        break
                # ans = min(ans, self.h[r])
                r -= self.lowbit(r)
            # ans = min(ans, self.a[r])
            if ans > self.a[r]:
                ans = self.a[r]
            if ans == self.mn:
                break
        return ans

    def lowbit(self, x):
        return x & -x

n, m = map(int, input().split())
maxlen = 10 ** 6
a = [maxlen] + list(map(int, input().split()))
q = []
for i in range(m):
    l, r = map(int, input().split())
    q.append((l, r, i))
q.sort(key=lambda x: x[1])
nums, r_ls = {}, [maxlen] * (n + 1)
for i in range(1, n + 1):
    if a[i] in nums:
        r_ls[i] = nums[a[i]]
    nums[a[i]] = i
ft = BinIndexTreeMin(n)
res, cur = [maxlen] * m, 1
for i in range(m):
    l, r, qi = q[i]
    while cur <= r:
        if r_ls[cur] != maxlen:
            ft.update(r_ls[cur], cur - r_ls[cur])
        cur += 1
    res[qi] = ft.query(l, r)
for i in range(m):
    print(res[i] if res[i] < maxlen else -1)