← 返回题目列表

Codeforces · 522/D

D. 最接近的等于

中文机器翻译题面 查看原题

给定序列 a1, a2, ..., an 和 m 查询 lj, rj (1 ≤ lj ≤ rj ≤ n)。对于每个查询,您需要打印这样一对元素 ax 和 ay (x ≠ y) 之间的最小距离,即:

- 元素的两个索引都在范围 [lj, rj] 内,即 lj ≤ x, y ≤ rj;
- 元素的值相等,即 ax = ay。

上面的文本将距离理解为 |x - y|。

输入

输入的第一行包含一对整数 n, m (1 ≤ n, m ≤ 5·105) — 相应地,序列的长度和查询的数量。

第二行包含整数序列 a1, a2, ..., an ( - 109 ≤ ai ≤ 109)。

接下来的 m 行包含查询,每行一个。每个查询由一对数字 lj, rj (1 ≤ lj ≤ rj ≤ n) 给出——查询范围限制的索引。

输出

打印 m 个整数 — 每个查询的答案。如果某些查询没有有效的匹配项,请打印 -1 作为此查询的答案。

示例

输入 #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