Cho một dãy ~n~ số nguyên ~a_1, a_2, \dots, 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 giữa hai phần tử ~a_x~ và ~a_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)~.

Input Specification

• Dòng đầu tiên gồm hai số nguyên dương ~n~ và ~m~.
• Dòng thứ hai gồm ~n~ số nguyên ~a_i~.
• ~m~ dòng tiếp theo gồm các truy vấn, mỗi truy vấn gồm hai số nguyên dương ~l_i, r_i~.

Output Specification

• 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.

Subtasks

• 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.

Constrains

• ~1 \le n, m \le 5 \cdot 10^5~
• ~-10^9 \le a_i \le 10^9~
• ~1 \le l_i \le r_i \le n~

Sample Cases

Input #1:

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

Output #1:

2
-1
1

Input #2:

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

Output #2:

2
3
2
2
-1