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

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.