Nhân dịp kỉ niệm ngày thành lập Đoàn Thanh niên Cộng sản Hồ Chí Minh, trường THPT Chuyên Tuyên Quang tổ chức trò chơi cho học sinh với luật chơi như sau: Có ~n~ quả bóng xếp thành một dãy được đánh số từ ~1~ đến ~n~, trong đó quả bóng thứ ~i~ có mã màu ~a_i~. Có ~m~ học sinh tham gia trò chơi, mỗi học sinh được chọn hai vị trí ~l, r~ trong dãy. Yêu cầu tìm khoảng cách nhỏ nhất giữa hai quả bóng có mã màu ~a_x~ và ~a_y~ sao cho:

• Cả hai quả bóng cùng nằm trong đoạn ~[l, r]~ (~l \le x, y \le r~);
• Hai quả bóng có cùng mã màu (~a_x = a_y~).

Yêu cầu: Với mỗi truy vấn, hãy tìm khoảng cách ~|x - y|~ nhỏ nhất thỏa mãn điều kiện.

Input

• Dòng đầu tiên chứa hai số nguyên dương ~n~ và ~m~ (~1 \le n, m \le 5 \times 10^5~).
• Dòng thứ hai chứa ~n~ số nguyên ~a_1, a_2, \dots, a_n~ (~1 \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_i, r_i~ (~1 \le l_i \le r_i \le n~).

Output

• Ghi ra ~m~ dòng, 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 mãn điều kiện thì in ra ~-1~.

Sample Input 1

7 1
1 0 1 2 3 4 2
1 4

Sample Output 1

2

Sample Input 2

12 3
1 4 2 11 2 3 3 10 5 3 6 3
1 12
2 4
6 12

Sample Output 2

1
-1
1