Cho dãy số ~a_1~, ~a_2~, ..., ~a_n~ ~(|a_i| \le 15000, n \le 50000)~.

Hàm ~q(x, y)~ = ~max~ {tổng(~a_i~+~a_{i + 1}~+...+~a_j~), ~x \le i \le j \le y~ }.

Cho ~m~ câu hỏi dạng ~x~, ~y~ ~(1 \le x \le y \le n)~. ~(m \le 50000)~, hãy tính các ~q(x, y)~.

Input

• Dòng đầu là ~n~.
• Dòng thứ hai là dãy ~a~.
• Dòng thứ 3 là ~m~.
• ~m~ dòng tiếp theo mỗi dòng là 1 cặp số ~x~, ~y~.

Output

• Lần lượt ghi ra các ~q(x, y)~ tương ứng. Mỗi kết quả ghi ra trên 1 dòng.

Sample Input

3
-1 2 3
1
1 2

Sample Output

2