You are given sequence a₁, a₂, ..., 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⁵) — the length of the sequence and the number of queries, correspondingly.

The second line contains the sequence of integers a₁, a₂, ..., a_n ( - 10⁹ ≤ a_i ≤ 10⁹).

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.

Closest Equals

Examples