Closest Equals

Problem Description

You are given a sequence $a$ indexed from $1$ to $n$, and then $m$ queries.

Each query gives a range $[l, r]$; find the minimum distance between two equal elements $a_i$ and $a_j$ within the range — that is, find a pair $(a_i, a_j)$ such that:

• $a_i = a_j$;
• $l \le i, j \le r$ ($i \neq j$);

and minimize $|i - j|$. If no two equal elements exist in the range, output $-1$.

Input Format

The first line contains two integers $n, m$ with $1 \le n, m \le 5 \times 10^5$.

The second line contains $n$ integers $a_i$ with $1 \le a_i \le 10^9$.

Each of the next $m$ lines contains two integers $l, r$ with $1 \le l \le r \le n$.

Output Format

Output $m$ lines, each containing one integer: the answer to the query.

Sample Input 1

5 3
1 1 2 3 2
1 5
2 4
3 5

Sample Output 1

1
-1
2

Sample Input 2

6 5
1 2 1 3 2 3
4 6
1 3
2 5
2 4
1 6

Sample Output 2

2
2
3
-1
2