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 os, sys
from io import BytesIO, IOBase
from types import GeneratorType
from typing import Counter

def bootstrap(f, stack=[]):
    def wrappedfunc(*args, **kwargs):
        if stack:
            return f(*args, **kwargs)
        else:
            to = f(*args, **kwargs)
            while True:
                if type(to) is GeneratorType:
                    stack.append(to)
                    to = next(to)
                else:
                    stack.pop()
                    if not stack:
                        break
                    to = stack[-1].send(to)
            return to
    return wrappedfunc

class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, 8192))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, 8192))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)

class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")

sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
if sys.hexversion == 50858480:
    sys.stdin = open('/Users/zhang-wangz/Desktop/algorithm/tea_0x3f/00_cfinput.txt')

def queryInteractive(a, b, c):
    print('? {} {} {}'.format(a, b, c))
    sys.stdout.flush()
    return int(input())

def answerInteractive(x1, x2):
    print('! {} {}'.format(x1, x2))
    sys.stdout.flush()

input = lambda: sys.stdin.readline().strip()
ints = lambda: list(map(int, input().split()))
Int = lambda: int(input())
inf = float('inf')

'''
输入 n(2≤n≤2e5) 和 m(1≤m≤2e5)；然后输入一个长为 n 的数组 a(-1e9≤a[i]≤1e9)，数组下标从 1 开始；
然后输入 m 个询问，每个询问表示一个数组 a 内的闭区间 [L,R] (1≤L≤R≤n)。
对每个询问，输出区间内的相同元素下标之间的最小差值，如果区间内不存在相同元素，输出 -1。
'''

class ST:
    # go使用seg [] l,r,val 来代替了初始化（build的时候传入1，n)
    def __init__(self, n: int):
        self.n = n
        self.val = [10**9] * (n * 4)

    # 这里的l，r就是传入1，n
    def update(self, o: int, l: int, r: int, idx: int, val: int) -> None:
        if l == r:
            self.val[o] = val
            return
        m = (l + r) // 2
        # 因为go build的时候传入l，r然后build左右部分是(l,m) | (m+1,r)
        if idx <= m: self.update(o<<1, l, m, idx, val)
        else: self.update(o<<1|1, m + 1, r, idx, val)
        self.val[o] = min(self.val[o<<1], self.val[o<<1|1])

    def query(self, o: int, l: int, r: int, L: int, R: int) -> int:
        if L <= l and r <= R: return self.val[o]
        m = (l + r) // 2
        # R <= m 说明最小值在左边
        if R <= m: return self.query(o<<1, l, m, L, R)
        # m < L 说明最小值在右边
        if m < L: return self.query(o<<1|1, m + 1, r, L, R)
        return min(self.query(o<<1, l, m, L, R), self.query(o<<1|1, m + 1, r, L, R))

def solve():
    n, m = ints()
    a = [0] + ints() # 从1开始
    ret = [0] * m
    q = [[] for _ in range(n+1)]
    for i in range(m):
        l, r = ints()
        q[r].append((l, i))
    
    sg = ST(n)
    last = Counter()
    for i in range(1, n+1):
        tp = last[a[i]]
        if tp > 0:
            sg.update(1, 1, n, tp, i-tp)
        for p in q[i]:
            res = sg.query(1, 1, n, p[0], i)
            if res == 10**9:
                res = -1
            ret[p[1]] = res
        last[a[i]] = i
    print("\n".join(map(str, ret)))
solve()