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\).

Ví dụ

Input:

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

Output:

4
4
5

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.