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 ai (−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.