给定序列 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