Lan là một sinh viên chuyên ngành kinh tế. Kỳ này Lan bắt đầu tham gia thực tập tại kho hàng của một xí nghiệp vận chuyển X. Trong kho hàng này có ~n~ thùng hàng, thùng hàng thứ ~i~ có trọng lượng là ~w_i~. Ngày đầu tiên đi thực tập, Lan được người phụ trách kho đưa cho một tờ phiếu và yêu cầu điền đầy đủ thông tin vào phiếu đó giúp ông ta. Trên tờ phiếu ghi ~Q~ yêu cầu, mỗi yêu cầu có dạng ~(a, b)~: cho biết khối lượng lớn nhất của các thùng hàng từ thùng hàng thứ ~a~ đến thùng hàng thứ ~b~. Để công việc ngày đầu thực tập được diễn ra thuận lợi và nhanh chóng, bạn hãy giúp Lan điền đầy đủ thông tin vào phiếu trên nhé.

Yêu cầu: Tìm khối lượng lớn nhất của các thùng hàng từ thùng hàng thứ ~a~ đến thùng hàng thứ ~b~ trong ~Q~ yêu cầu được ghi trên phiếu.

Input

• Dòng 1 chứa 2 số nguyên dương ~n~ và ~Q~ (~1 \le n \le 50000~; ~1 \le Q \le 200000~) cách nhau một dấu cách;
• ~n~ dòng tiếp theo, dòng thứ ~i~ chứa số nguyên dương ~w_i~ (~1 \le w_i < 10^6~);
• ~Q~ dòng tiếp theo, mỗi dòng chứa hai số nguyên dương ~a~ và ~b~ (~1 \le a \le b \le n~) cách nhau 1 dấu cách là yêu cầu tìm khối lượng lớn nhất của các thùng hàng từ thùng hàng thứ ~a~ đến thùng hàng thứ ~b~.

Output

• Gồm ~Q~ dòng chứa giá trị lớn nhất tìm được tương ứng với ~Q~ yêu cầu.

Sample Input 1

5 2
2
3
4
1
4
1 3
4 4

Sample Output 1

4
1