Đề bài được tóm tắt theo trí nhớ.

Cho số nguyên dương ~n~ (~1 \le n \le 10^5~) và mảng ~a~ nguyên dương ~a_1, a_2, ..., a_n~ (~a_i \le 10^9~) phân biệt.

Cho ~q~ truy vấn, mỗi truy vấn gồm hai số ~i~ ~j~ (~1 \le i < j \le n~).

Yêu cầu: Tìm đoạn con dài nhất chứa hai chỉ số ~i~ và ~j~ sao cho:

• Nếu ~a_i < a_j~ thì tất cả các phần tử trong đoạn đó nhận ~a_i~ làm GTNN, ~a_j~ làm GTLN.
• Nếu ~a_j < a_i~ thì tất cả các phần tử trong đoạn đó nhận ~a_j~ làm GTNN, ~a_i~ làm GTLN.

INPUT

Dòng đầu tiên nhập vào hai số nguyên dương ~n~ và ~q~ (~n, q \le 10^5~)

Dòng thứ hai nhập vào ~n~ số nguyên dương ~a_1, a_2, ..., a_n~ (~a_i \le 10^9~). Dữ liệu đảm bảo các số nguyên dương ~a_1, a_2, ..., a_n~ phân biệt.

~q~ dòng tiếp theo, mỗi dòng chứa hai số nguyên dương ~i, j~ (~i < j~).

OUTPUT

In ra ~q~ dòng, mỗi dòng ghi hai số nguyên dương lần lượt là chỉ số đầu và chỉ số cuối của đoạn con thu được thỏa mãn yêu cầu đề bài. Nếu không có phương án thỏa mãn, in ra ~-1~.

SAMPLE INPUT

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

SAMPLE OUTPUT

2 6
2 7
-1

SUBTASKS