给出 n 个数的序列，每次询问给定两个数 [l,r] ，你需要从 l 到 r 这个区间里面取任意个数（可以不取），求选取的数的和的最大值。
其中不选取数的时候，和为 0。
第 1 行一个正整数 n 代表序列长度。
第 2 行 n 个数代表序列 a_1, a_2, ..., a_n 。
第 3 行一个正整数 q 代表询问组数。
接下来 q 行，每行两个数 l, r ，代表一组询问区间的端点。
q 行，每行一个整数代表答案。
6 2 -1 2 3 -5 2 3 1 2 1 3 2 4
2 4 5
对于 80% 的数据保证 1≤n,q≤10^5 。
对于 100% 的数据保证 1≤n,q≤10^6,0≤∣a_i∣≤10^9,1≤l≤r≤n 。