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 SegmentTree:
    def __init__(self, data, func):
        self.data = data
        self.n = len(data)
        self.tree = [None] * (4 * self.n)
        self._merge = func
        if self.n:
            self._build(0, 0, self.n-1)

    def query(self, ql, qr):
        return self._query(0, 0, self.n-1, ql, qr)

    def update(self, index, value):
        self.data[index] = value
        self._update(0, 0, self.n-1, index)

    def _build(self, tree_index, l, r):
        if l == r:
            self.tree[tree_index] = self.data[l]
            return
        mid = (l+r) // 2
        left, right = 2 * tree_index + 1, 2 * tree_index + 2
        self._build(left, l, mid)
        self._build(right, mid+1, r)
        self.tree[tree_index] = self._merge(self.tree[left], self.tree[right])

    def _query(self, tree_index, l, r, ql, qr):
        if l == ql and r == qr:
            return self.tree[tree_index]
        mid = (l+r) // 2
        left, right = tree_index * 2 + 1, tree_index * 2 + 2
        if qr <= mid:
            return self._query(left, l, mid, ql, qr)
        elif ql > mid:
            return self._query(right, mid+1, r, ql, qr)
        return self._merge(self._query(left, l, mid, ql, mid),
                          self._query(right, mid+1, r, mid+1, qr))

    def _update(self, tree_index, l, r, index):
        if l == r == index:
            self.tree[tree_index] = self.data[index]
            return
        mid = (l+r)//2
        left, right = 2 * tree_index + 1, 2 * tree_index + 2
        if index > mid:
            self._update(right, mid+1, r, index)
        else:
            self._update(left, l, mid, index)
        self.tree[tree_index] = self._merge(self.tree[left], self.tree[right])

n, m = map(int, input().split())
a = [-1] + 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])
maxlen = 10 ** 6
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
st = SegmentTree([maxlen] * (n + 1), min)
res, cur = [maxlen] * m, 1
for i in range(m):
    l, r, qi = q[i]
    while cur <= r:
        if r_ls[cur] != maxlen:
            st.update(r_ls[cur], cur - r_ls[cur])
        cur += 1
    res[qi] = st.query(l, r)
for i in range(m):
    print(res[i] if res[i] < maxlen else -1)