Bình ghi lại nhiệt độ trong \(N\) ngày liên tiếp. Bạn hãy giúp Bình trả lời \(Q\) câu hỏi, mỗi câu hỏi yêu cầu tìm nhiệt độ cao nhất trong khoảng thời gian từ ngày \(l\) đến ngày \(r\).

Ràng buộc

Định dạng đầu vào

• Dòng đầu chứa hai số nguyên \(N\) và \(Q\) (\(1 \le N, Q \le 10^5\)).
• Dòng hai chứa \(N\) số nguyên \(a_1, a_2, \dots, a_N\) (\(1 \le a_i \le 10^9\)).
• \(Q\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(l, r\) (\(1 \le l \le r \le N\)).

Định dạng đầu ra

• Ứng với mỗi truy vấn, in ra giá trị lớn nhất tìm được trên một dòng.

Ví dụ

Input:

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

Output:

4
4
5