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.
'''
https://codeforces.com/problemset/problem/522/D

输入 n(≤5e5) 和 m(≤5e5)；然后输入一个长为 n 的数组 a(-1e9≤a[i]≤1e9)，数组下标从 1 开始；
然后输入 m 个询问，每个询问表示一个数组 a 内的闭区间 [L,R] (1≤L≤R≤n)。

对每个询问，输出区间内的相同元素下标之间的最小差值。
如果区间内不存在相同元素，输出 -1。

相似题目：https://www.luogu.com.cn/problem/P1972
输入
5 3
1 1 2 3 2
1 5
2 4
3 5
输出
1
-1
2

输入
6 5
1 2 1 3 2 3
4 6
1 3
2 5
2 4
1 6
输出
2
2
3
-1
2

https://codeforces.com/contest/522/submission/173138916

本题用到的技巧十分经典（指提示 4），如果你对此题没有思路，请务必掌握这一技巧。

提示 1：在相同元素中，只需要考虑相邻的元素。换句话说，这些元素对可以看成是若干线段。

提示 2：问题转换成查询区间内的最短线段。

提示 3：把询问离线，按照右端点排序。

提示 4：把提示 1 中的线段长度记录在线段的左端点上。

提示 5：遍历排序后的询问 [L,R]，如果位置 R 有线段的右端点，则更新线段左端点处的线段长度，我们最后要做的就是查询区间 [L,R] 内的最小值。

提示 6：用线段树实现。

线段长度可以一边遍历数组 a，一边用一个 last map 记录。
'''

from itertools import *
from collections import *
from math import *
from heapq import *
from functools import *
from bisect import *
from random import *
import sys
from typing import List

input = sys.stdin.readline


def solve():
    n, m = map(int, input().split())
    a = [0] + list(map(int, input().split()))
    q = []
    for i in range(m):
        l, r = map(int, input().split())
        q.append((i, l, r))

    # 根据查询区间的左端点排序
    q.sort(key=lambda x: x[2])

    # 计算每个点下一个相同的点的坐标
    dic = {}
    right = {}
    for i in range(n, 0, -1):
        if a[i] in dic:
            right[i] = dic[a[i]]
        dic[a[i]] = i

    N = n * 4
    f = [inf] * N
    nums = [inf] * (n + 1)

    def build(k, l, r):
        if l == r:
            f[k] = nums[r]
            return
        mid = l + r >> 1
        build(k << 1, l, mid)
        build(k << 1 | 1, mid + 1, r)
        f[k] = min(f[k << 1], f[k << 1 | 1])

    def add(k, l, r, x, y):
        if l == r:
            f[k] = min(f[k], y)
            return
        mid = l + r >> 1
        if x <= mid:
            add(k << 1, l, mid, x, y)
        else:
            add(k << 1 | 1, mid + 1, r, x, y)
        f[k] = min(f[k << 1], f[k << 1 | 1])

    def calc(k, l, r, x, y):
        if l == x and r == y:
            return f[k]
        mid = l + r >> 1
        if y <= mid:
            return calc(k << 1, l, mid, x, y)
        elif x >= mid + 1:
            return calc(k << 1 | 1, mid + 1, r, x, y)
        else:
            return min(calc(k << 1, l, mid, x, mid), calc(k << 1 | 1, mid + 1, r, mid + 1, y))

    # 建树
    build(1, 1, m)
    j = 1
    res = [0] * m
    # 存储当前不合适的
    heap = []
    for i, l, r in q:
        # 看看是否有前面合适的
        while heap and heap[0][0] <= r:
            r0, l0 = heappop(heap)
            add(1, 1, n, l0, r0 - l0)
        while j <= r:
            if j in right:
                if right[j] <= r:
                    add(1, 1, n, j, right[j] - j)
                else:  # 另一个点超过了r，先存到heap中
                    heappush(heap, (right[j], j))
            j += 1
        res[i] = calc(1, 1, n, l, r)

    # 输出
    for v in res:
        if v == inf:
            print(-1)
        else:
            print(v)


solve()
