Cho một dãy ~n~ số nguyên ~a_1, a_2, \ldots , a_n~ và ~m~ truy vấn ~l_j, r_j~ ~(1 \le l_j \le r_j \le n)~. Với mỗi truy vấn, bạn cần tìm khoảng cách nhỏ nhất ~|x - y|~ giữa hai phần tử ~a_x~ và ~a_y~ ~(x \ne y)~ sao cho:

• cả hai phần tử đều nằm trong đoạn ~[l_j, r_j]~ ~(l_j \le x, y \le r_j)~;

• hai phần tử đều có giá trị bằng nhau ~(a_x = a_y)~.

Dữ liệu

• Dòng đầu tiên gồm hai số nguyên dương ~n~ và ~m~ ~(1 \le n, m \le 5 \cdot 10^5)~.

• Dòng thứ hai gồm ~n~ số nguyên ~a_1, a_2, \ldots, a_n~ ~(-10^9 \le a_i \le 10^9)~.

• ~m~ dòng tiếp theo, mỗi dòng gồm hai số nguyên dương ~l_j, r_j~ ~(1 \le l_j \le r_j \le n)~ mô tả một truy vấn.

Kết quả

• Gồm ~m~ dòng, trong đó dòng thứ ~i~ là khoảng cách ~|x -y|~ nhỏ nhất tìm được trong truy vấn thứ ~i~. Nếu không có cặp nào thỏa điều kiện thì in ra ~-1~.

Ràng buộc

• Subtask 1 (20%): ~1 \le n, m \le 100~.

• Subtask 2 (20%): ~1 \le n, m \le 1000~.

• Subtask 3 (60%): Không có ràng buộc gì thêm.

Ví dụ

Sample Input 1

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

Sample Output 1

2
-1
1

Sample Input 2

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

Sample Output 2

2
3
2
2
-1