给出n个数的序列，每次询问给定两个数[l, r]，你需要从al到ar这个区间里面取任意个数（可以不取），求选取的数的和的最大值。其中不选取数的时候，和为0。
例如，n=5， 给定的5个数字为5、8、9、10、11，对于区间[2, 4]，是指8、9、10，其最大和为27。
第1行一个正整数n代表序列长度, 1<= n <= 1000000.
第2行n个数代表序列a1、a2、...、an, 0 <= ai <= 1000000000.
第3行一个正整数q代表询问组数。
第4 ... q + 3行每行两个数l和r，代表一组询问区间的端点。1 <= l <= r <= n.
q行，每行一个整数代表答案。
6 2 -1 2 3 -5 2 3 1 2 1 3 2 4
2 4 5
奇遇编程