Tổng của một dãy con lớn nhất

Cho dãy số nguyên \(a\) gồm \(n\) phần tử, được đánh số từ \(1\) đến \(n\). Dãy con của \(a\) có thể thu được bằng cách xóa đi một số tùy ý các phần tử của nó. Ví dụ \(a = [1, 4, 3]\) có các dãy con là: \([1,4,3]\); \([1,4]\); \([1,3]\); \([4,3]\); \([1]\); \([4]\); \([3]\); \([\,]\).

Trọng số của một dãy là tổng các phần tử trong dãy (dãy rỗng có trọng số \(0\)).

Yêu cầu: Với mỗi truy vấn \((l, r)\), hãy tìm trọng số lớn nhất của một dãy con của dãy \(a_l, a_{l+1}, \ldots, a_r\).

Input

• Dòng đầu ghi số nguyên dương \(n\).
• Dòng thứ hai ghi \(n\) số nguyên \(a_1, a_2, \ldots, a_n\) (\(|a_i| \le 10^9\)).
• Dòng thứ ba ghi số nguyên dương \(T\) là số đoạn cần tính trọng số lớn nhất.
• Trong \(T\) dòng tiếp theo, mỗi dòng ghi hai số \(l\) và \(r\) (\(1 \le l \le r \le n\)).

Các số cách nhau một dấu cách.

Output

Gồm \(T\) dòng, mỗi dòng ghi một số nguyên là trọng số lớn nhất tương ứng với mỗi đoạn.

Scoring

• \(50\%\) số điểm: \(1 \le n, T \le 1000\).
• \(50\%\) số điểm: \(1000 < n, T \le 200\,000\).

Sample Input 1

6
4 5 -9 2 -6 1
2
1 3
2 5

Sample Output 1

9
7