CF522D.Closest Equals

You are given sequence _a_1, _a_2, ..., a__n and m queries l__j, r__j (1 ≤ l__j ≤ r__j ≤ n). For each query you need to print the minimum distance between such pair of elements a__x and a__y (x ≠ y), that:

• both indexes of the elements lie within range [l__j, r__j], that is, l__j ≤ x, y ≤ r__j;
• the values of the elements are equal, that is a__x = a__y.

The text above understands distance as |x - y|.

给你一个序列 $a_1, a_2, \dots, a_n$ 和 $m$ 个查询 $l_j, r_j$（满足 $1 \le l_j \le r_j \le n$）。对每个查询，你需要输出满足以下条件的两个元素 $a_x$ 和 $a_y$（其中 $x \ne y$）之间的最小距离：

• 两个元素的下标均落在区间 $[l_j, r_j]$ 内，即 $l_j \le x, y \le r_j$；
• 两个元素的值相等，即 $a_x = a_y$。

上文中“距离”定义为 $|x - y|$。

The first line of the input contains a pair of integers n, m (1 ≤ n, m ≤ 5·105) — the length of the sequence and the number of queries, correspondingly.

The second line contains the sequence of integers _a_1, _a_2, ..., a__n ( - 109 ≤ a__i ≤ 109).

Next m lines contain the queries, one per line. Each query is given by a pair of numbers l__j, r__j (1 ≤ l__j ≤ r__j ≤ n) — the indexes of the query range limits.

输入的第一行包含两个整数 $n$、$m$（$1 ≤ n, m ≤ 5·10^5$），分别表示序列的长度和查询次数。

第二行包含一个整数序列 $a_1, a_2, ..., a_n$（$-10^9 ≤ a_i ≤ 10^9$）。

接下来 $m$ 行，每行包含一个查询。每个查询由一对数字 $l_j, r_j$（$1 ≤ l_j ≤ r_j ≤ n$）给出，表示查询区间的左右端点索引。

Print m integers — the answers to each query. If there is no valid match for some query, please print -1 as an answer to this query.

输出 m 个整数——每个查询的答案。如果某个查询不存在有效的匹配，请输出 -1 作为该查询的答案。