You are given sequence a1,a2,...,an and m queries lj,rj (1 \le lj \le rj \le n). For each query you need to print the minimum distance between such pair of elements ax and ay (x \neq y), that:
both indexes of the elements lie within range [lj,rj], that is, lj \le x,y \le rj; the values of the elements are equal, that is ax=ay.
The text above understands distance as |x-y|.

The first line of the input contains a pair of integers n, m (1 \le n,m \le 5 \cdot 105) - the length of the sequence and the number of queries, correspondingly.

The second line contains the sequence of integers a1,a2,...,an (-109 \le ai \le 109).

Next m lines contain the queries, one per line. Each query is given by a pair of numbers lj,rj (1 \le lj \le rj \le 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.