Ngân được giao nhiệm vụ xây dựng một hệ thống quản lý tài sản cho một công ty. Công ty này quản lý nhiều loại tài sản khác nhau, mỗi loại tài sản có giá trị thay đổi theo thời gian. Ban quản lý muốn biết trong một khoảng thời gian cụ thể, giá trị cao nhất mà một chuỗi tài sản có thể đạt được là bao nhiêu.

Công ty đã theo dõi các thay đổi về giá trị của tài sản theo thời gian và lưu trữ chúng dưới dạng một mảng. Ngân được yêu cầu thực hiện nhiều truy vấn khác nhau, mỗi truy vấn đưa ra một khoảng thời gian và yêu cầu Ngân tìm chuỗi tài sản có tổng giá trị cao nhất trong khoảng đó.

Vấn đề: Ngân được cung cấp một mảng \(A\) gồm \(n\) số nguyên, đại diện cho giá trị của các loại tài sản tại các thời điểm khác nhau. Ngân cần thực hiện \(q\) truy vấn, mỗi truy vấn yêu cầu tìm tổng giá trị lớn nhất của một đoạn liên tiếp trong mảng \(A\) từ chỉ số \(l\) đến \(r\).

\(max(A_i + A_{i+1}+...+A_j)\) với \(l \le i \le j \le r\)

Truy vấn cụ thể: Mỗi truy vấn sẽ yêu cầu: Tìm chuỗi con liên tiếp từ mảng \(A\) nằm trong khoảng chỉ số từ \(l\) đến \(r\), sao cho tổng giá trị của chuỗi con này là lớn nhất.

Dữ liệu vào

• Dòng đầu tiên gồm \(1\) số nguyên \(n\)
• Dòng thứ hai gồm \(n\) số nguyên \(A_i\)
• Dòng thứ ba là số nguyên \(q\)
• \(q\) dòng tiếp theo, mỗi theo gồm \(2\) số nguyên \(l,r\) một truy vấn.

Dữ liệu ra

• In ra \(q\) số nguyên là đáp án cho \(q\) truy vấn.

Điều kiện

• \(1 \le n,q \le 10^5\)
• \(1 \le l,r \le n\)
• \(0 \le |A_i| \le 10^9\)

Input 1

3
-1 2 3
1
1 2

Output 1

2