Trong một lần đi hội chợ, Nam tham gia trò chơi trúng thưởng với luật chơi được mô tả như sau: Có một băng số hình chữ nhật được chia ra làm ~N~ ô vuông, đánh số từ trái qua phải bắt đầu từ ~1~ đến ~N~. Trên ô vuông thứ ~i~ người ta ghi một số nguyên ~a_i ~ (~1 \leq i \le N~). Ở một lượt chơi, trước tiên người chơi sẽ được ban tổ chức cho bốc thăm để nhận được hai số nguyên dương ~x~, ~y~ (~1 \le x \le y \le N~), sau đó trong phạm vi dãy ô từ ~a_x ~ đến ~a_y~, người chơi được quyền lựa chọn một dãy các ô liên tiếp nhau; giả sử theo thứ tự từ trái qua phải, người chơi lựa chọn dãy các ô ~a_i, a_{i+1}, …, a_{i+k} ~; khi đó điểm số mà người chơi đạt được sẽ là:
~a_i + a_{i+1}+ … + a_{i+k}~ (~x \le i \le i+k \le y~)
Yêu cầu
Với hai số ~x~, ~y~ bốc thăm được từ một lượt chơi, hãy tính số điểm lớn nhất mà Nam có thể đạt được.
Dữ liệu
Vào từ file văn bản ~DIEMSO.INP~ có nội dung:
Dòng đầu tiên chứa số nguyên dương ~N~ (~1 \le N \le 5 \times 10^4~ ) là số lượng ô của băng số;
Dòng thứ hai chứa ~N~ số nguyên ~a_1, a_2, ..., a_N ~ (~ \left | a_i \right | \le 10^7 ~) là các số ghi trên băng số;
Dòng thứ ba chứa số nguyên dương ~M~ (~1 \le M \le 5~) là số lượt chơi mà Nam tham gia;
Trong ~M~ dòng tiếp theo; dòng thứ ~i~ ghi hai số ~x_i~, ~y_i~ là hai số Nam bốc thăm được ở lượt chơi thứ ~i~.
Các số trên cùng dòng viết cách nhau ít nhất một dấu cách.
Kết quả
Ghi ra file văn bản ~DIEMSO.OUT~ gồm ~M~ dòng, mỗi dòng là điểm số lớn nhất mà Nam có thể đạt được tương ứng với lượt chơi trong file ~DIEMSO.INP~.
Sample Input
5
-2 -6 7 -5 10
2
2 3
1 5
Sample Output
7
12
Bình luận