Cho một dãy \(n\) số nguyên \(a_1, a_2,..., a_n\) và \(m\) truy vấn \(L_j, R_j (1 ≤ L_j ≤ R_j ≤ n)\).

Với mỗi truy vấn, tìm khoảng cách nhỏ nhất \(|x-y|\) 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 ≤ x, y ≤ 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 ≤ n, m ≤ 5 * 10^5 ).\)

• Dòng thứ hai gồm \(n\) số nguyên \(a_i (−10^9 ≤ a_i ≤ 10^9 ).\)

• \(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 (1 ≤ L_i ≤ R_i ≤ 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% số điểm với \(1≤n,m≤100.\)

• Subtask 2: 20% số điểm với \(1≤n,m≤1000.\)

• Subtask 3: 60% số điểm không có ràng buộc gì thêm.

Sample INput

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

Sample Output

2 
-1
1