Closest Equals

题面翻译

现在有一个序列 $a_1, a_2, ..., a_n$ ，还有$m$个查询 $l_j, r_j$ $(1 ≤ l_j ≤ r_j ≤n)$ 。对于每一个查询，请找出距离最近的两个元素 $a_x$ 和 $a_y$$(x ≠ y)$ ，并且满足以下条件：

$l_j ≤ x, y ≤ r_j$;

$a_x = a_y$。

两个数字的距离是他们下标之差的绝对值 $|x − y|$ 。

题目描述

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|$ .

输入格式

The first line of the input contains a pair of integers $n$ , $m$ ( $1<=n,m<=5·10^{5}$ ) — 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}$ ( $-10^{9}<=a_{i}<=10^{9}$ ).

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.

输出格式

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.

样例 #1

样例输入 #1

5 3
1 1 2 3 2
1 5
2 4
3 5

样例输出 #1

1
-1
2

样例 #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