Cho mảng ~a_1,a_2,\ldots,a_n~ gồm các số nguyên dương phân biệt và ~q~ truy vấn. Mỗi truy vấn gồm hai chỉ số ~i,j~ với ~i<j~.</p>

Cần tìm đoạn con dài nhất chứa hai chỉ số ~i,j~ sao cho mọi phần tử trong đoạn đều nằm giữa hai giá trị ~a_i~ và ~a_j~. Nếu không tồn tại đoạn thỏa mãn, in ra ~-1~.

Input

Dòng đầu chứa hai số nguyên dương ~n,q~.

Dòng thứ hai chứa ~n~ số nguyên dương phân biệt ~a_i~.

~q~ dòng tiếp theo, mỗi dòng chứa hai chỉ số ~i,j~.

Output

Với mỗi truy vấn, in ra hai chỉ số đầu và cuối của đoạn tìm được, hoặc ~-1~ nếu không có phương án.

Subtask

• 20% số điểm: ~q=1~, ~n \le 10^2~.
• 20% số điểm: ~q=1~, ~n \le 10^4~.
• 20% số điểm: ~q \le 10^2~.
• 40% số điểm: ~n,q \le 10^5~, ~a_i \le 10^9~.

Ví dụ

8 3
10 7 4 5 8 6 3 20
3 5
5 7
2 6

2 6
2 7
-1