GSS Đoạn con có tổng lớn nhất

Cho dãy số a[1], a[2], ..., a[n] Hàm

q(x, y) = max{tổng(a[i]+a[i+1]+...+a[j]), x <= i <= j <= y }.

Cho m câu hỏi dạng x, y -> hãy tính các q(x, y). 

Input

·        Dòng đầu là n ≤ 50000

·        Dòng thứ hai là dãy a.(|a[i]| ≤ 15000).

·        Dòng thứ 3 là m.(m <= 50000)

·        m dòng tiếp theo mỗi dòng là 1 cặp số x, y.(1 ≤ x ≤ y ≤ n).

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

Input	Output
3 -1 2 3 1 1 2	2

 

Giới hạn: 75% test có n, m ≤ 100.