给定一个下标从 $1$ ~ $n$ 的序列 $a$,然后进行 $m$ 次询问。
每次询问给出一对 $[l, r]$,找到区间中数值相等的且距离最相近的两个数 $a_i$ 和 $a_j$,求它们的距离。
换言之找到一组数 $(a_i, a_j)$ 满足
$a_i = a_j$;
$l \leq i, j \leq r$ $(i \neq j)$;
求 $|i - j|$ 的最小值,如果区间中不存在相等的两个数,则输出 $-1$。
输入格式
第一行输入两个整数 $1 \leq n, m \leq 5 \times 10^5$。
第二行输入 $n$ 个整数 $1 \leq a_i \leq 10^9$。
接下来 $m$ 行,每行输入两个整数 $1 \leq l \leq r \leq n$。
输出格式
输出 $m$ 行,每行包含一个整数作为询问的答案。
输入样例1
5 3
1 1 2 3 2
1 5
2 4
3 5
输出样例1
1
-1
2
输入样例2
6 5
1 2 1 3 2 3
4 6
1 3
2 5
2 4
1 6
输出样例2
2
2
3
-1
2