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\).

Sample Input

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

Sample Output

2 
-1
1

Sample Input

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

Sample Output

2 
3 
2 
2
-1

Ràng buộc :

• Subtask 1(20%): 1 ≤ n, m ≤ 100. 
• Subtask 2(20%): 1 ≤ n, m ≤ 1000. 
• Subtask 3(60%): Không có ràng buộc gì thêm.