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·105) — the length of the sequence and the number of queries, correspondingly. The second line contains the sequence of integers a1, a2, ..., an ( - 109 ≤ ai ≤ 109). Next m lines contain the queries, one per line. Each query is given by a pair of numbers lj, rj (1 ≤ lj ≤ rj ≤ 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.