Thời đại công nghệ phát triển, trí tuệ con người đã có những chuyển biến đột phá. Bidibidi, một nhà khoa học mới nổi, các thành phẩm nghiên cứu của ông mang lại nhiều thành tựu to lớn và khai phá nhiều lĩnh vực mà con người bấy lâu nay còn đang dang dở. Mới đây một phát minh gây sốc của ông là tái tạo lại trái đất thời nguyên thủy, ông xây dựng một mô hình nhỏ có đầy đủ hệ sinh thái và tài nguyên tựa như trái đất phiên bản nhỏ, đồng thời ông còn có thể tùy chỉnh được thời không trong mô hình mà mình tạo ra giúp cho thời gian bên trong mô hình nhanh hơn ở ngoài gấp nhiều lần. Trong một lần thí nghiệm, ông vô tình khiến cho thời gian bên trong mô hình hoàn toàn vượt xa thế giới thực, sự sống đã tồn tại trong mô hình ấy. Khác với địa cầu, động vật có trí thông minh trong thế giới của ông lại là loài Nấm chúng vô cùng nhỏ bé nhưng lại rất thông minh. Cụ thể, chúng hình thành một quần thể và bắt đầu mở rộng lãnh thổ của mình sang các vùng lân cận khác. Chúng khoanh vùng ~n~ địa điểm và sắp xếp những nơi cần chiếm đóng thành một hàng ngang và được đánh số từ ~1~ đến ~n~ đồng thời mỗi khu vực được chúng quy ước mức độ phong phú của tài nguyên bằng số ~a_i~. Sau tất cả chúng họp bàn với nhau rằng nơi nào sẽ được chiếm đóng, mọi Nấm đều có suy nghĩ riêng chúng, đã có ~q~ đề xuất sẽ khai thác nơi tài nguyên phong phú nhất từ khu vực thứ ~l_i~ đến ~r_i~. Số lượng các ý kiến quá lớn các Nấm không thể xử lý hết, bạn hãy giúp chúng trả lời kết quả mà chúng mong muốn.

Input

Dòng đầy tiên là cặp giá trị ~n~ và ~q~.

Dòng thứ hai, Gồm ~n~ giá trị ~a_i~.

~q~ dòng tiếp theo, gồm các giá trị ~l_i~ và ~r_i~ đại diện đề xuất thứ ~i~.

Output

Gồm ~q~ dòng, Ứng với mỗi đề xuất của các Nấm hãy đưa ra kết quả cần thiết.

Constraints

~1 \le n, q \le 10^5~

~1 \le a_i \le 10^5~

~1 \le l_i \le r_i \le n~

Input Sample 1

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

Output Sample 1

3
2
5

Subtask

• SubTask ~1~: ~90~% số test ứng với ~q \le 10^3~
• SubTask ~2~: ~10~% số test còn lại, không ràng buộc gì thêm