1508: cyw 的抽奖盒
Time Limit: 1 Sec
Memory Limit: 256 MB
Submission：5
AC：3
Score：100.00
cyw 在游戏中获得了一个抽奖机会！
现在有 n 个抽奖盒，编号分别为 1,2,3 ... n
cyw 会获得一个被允许取抽奖盒的区间 [l,r]，也就是她只能从 a_l ~ a_r 这个区间编号的抽奖盒中任意选择一些抽奖盒打开
而这些抽奖盒中，有些是奖励金币，有些却是扣除金币，现在 cyw 通过她的小伙伴得知了每个抽奖盒内的情况 a_i
若 a_i > 0 则表示奖励 a_i 个金币
若 a_i < 0 则表示扣除 a_i 个金币
现在 cyw 想预先知道，对于某个区间她最多可以获得多少个金币？
当然 cyw 是可以一个抽奖盒都不选的，此时她不会获得金币，即获得 0 个金币
第 1 行一个正整数 n 代表抽奖盒数量。
第 2 行 n 个数代表序列 a_1, a_2, ..., a_n 。
第 3 行一个正整数 q 代表询问组数。
第 4 ... q + 3 行每行两个数 l, r 代表一次询问的区间 [l,r]。
对于 30% 的数据保证 1 <= n <= 100, 1 <= q <= 1000 。
对于 100% 的数据保证 1 <= n, q<= 10^6, 0 <= |a_i| <= 10^9, 1<= l <= r <= n 。
输出 q 行每行一个整数表示对应区间内 cyw 最多能获得的金币数量。
input:
6
2 -1 2 3 -5 2
3
1 2
1 3
2 4
output:
2
4
5