Cho một mảng ~a~ gồm ~n~ phần tử và ~q~ truy vấn có dạng:

• "~l~ ~r~": Trong các đoạn con ~a_x, a_{x+1}, \ldots, a_y~ mà ~l \le x \le y \le r~, đoạn nào có tổng các phần tử lớn nhất?

Yêu cầu: Với mỗi truy vấn, bạn hãy tìm giá trị của tổng đoạn có tổng lớn nhất đó.

Input

• Dòng đầu tiên chứa số ~n~ ~(1 \le n \le 50\,000)~.
• Dòng thứ hai chứa ~n~ số ~a_1, a_2, \ldots, a_n~ là các phần tử của mảng ~(-40\,000 \le a_i \le 40\,000)~.
• Dòng thứ ba chứa số ~q~ ~(1 \le q \le 10^5)~.
• ~q~ dòng tiếp theo, mỗi dòng chứa hai số ~l~ và ~r~ ~(1 \le l \le r \le n)~ mô tả một truy vấn.

Output

• Với mỗi truy vấn, in ra đáp án của truy vấn đó trên một dòng.

Sample Input

10
5 18 12 -3 -19 6 -7 -10 -16 -10
10
1 10
2 8
9 10
3 7
4 6
7 9
1 4
2 10
3 9
1 5

Sample Output

35
30
-10
12
6
-7
35
30
12
35