Lan là một sinh viên chuyên ngành kinh tế. Kỳ học này Lan bắt đầu 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ó khối 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 đó. Trên tờ phiếu ghi \(q\) yêu cầu, mỗi yêu cầu có dạng \((a,b)\) - tìm khối lượng của thùng hàng nặng nhất trong các thùng hàng từ thùng hàng thứ \(a\) đến thùng hàng thứ \(b\). Để công việc thực tập được diễn ra thuận lợi và nhanh chóng, anh (chị) hãy giúp Lan điền đầy đủ thông tin vào phiếu trên.

Yêu cầu: Tìm khối lượng của thùng hàng nặng nhất trong 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

Dữ liệu:

+ Dòng 1 chứa 2 số nguyên dương \(n\) và \(q\) \((1 \leq n \leq 50000;\ 1 \leq q \leq 200000)\) cách nhau một khoảng trắng;

+ Dòng thứ \(i\) trong \(n\) dòng tiếp theo chứa số nguyên dương \(w_{i}\ (1\ w_{i} < 1000000)\);

+ \(q\) dòng tiếp theo mỗi dòng chứa hai số nguyên dương \(a\) và \(b\) \((1 \leq a \leq b \leq n)\) cách nhau 1 dấu cách là yêu cầu tìm khối lượng của thùng hàng nặng nhất trong các thùng hàng từ thùng hàng thứ \(a\) đến thùng hàng thứ \(b\).

Kết quả:

+ Ghi \(q\) dòng chứa giá trị lớn nhất tìm được tương ứng với \(q\) yêu cầu.

Ví dụ:

Ràng buộc:

• 20% số test có \(1 \leq n,\ q \leq 1000\).

• 40% số test có \(1 \leq n,\ q \leq 10000\).

• 40% số test không có thêm ràng buộc khác