给定一个下标从 $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