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

Input

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.

Output

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.