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

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