该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

在一个阳光明媚的日子里，蒜头君和花椰妹在花园里找到了一张藏宝图。这张藏宝图上标记着许多不同的宝藏点，宝藏点上写着一些数字。蒜头君和花椰妹决定一起玩一个游戏，他们会根据藏宝图上给出的线索，从一处宝藏点走到另一处宝藏点，沿途会收集到一些宝藏数字。 他们可以选择收集其中的某些宝藏数字，也可以一个都不收集。他们想知道，如果他们想要自己的收集的宝藏数字之和最多，应该收集哪些宝藏数字呢？ 现在，蒜头君和花椰妹需要你的帮助，你能帮他们计算出他们每次冒险能收集的宝藏数字之和的最大值是多少吗？

举例说明： 当n=5，序列为1 2 3 4 5时，对于区间[1,3]，收集该区间内所有数的和为1+2+3=6，这是能收集到的最大和。

输入格式

第 1 行一个正整数 n 代表序列长度。 第 2 行 n 个数代表序列 a1,a2,⋯,an。 第 3 行一个正整数 q 代表询问组数。 第 4 到 q+3 行每行两个数 l,r 代表一组询问区间的端点。

输出格式

q 行每行一个整数代表对应询问的答案。

样例输入

6
2 -1 2 3 -5 2
3
1 2
1 3
2 4

样例输出

2
4
5

样例解释

样例中序列长度为6，序列为[2, -1, 2, 3, -5, 2]，共有3组询问：

1. 询问区间[1,2]：可选择的收集组合有只收集2（和为2）、只收集-1（和为-1）、收集2和-1（和为1）、一个都不收集（和为0），其中最大的和为2；
2. 询问区间[1,3]：所有可选收集组合中，收集2和2（即序列第1位和第3位）的和为4，是该区间能收集到的最大和；
3. 询问区间[2,4]：所有可选收集组合中，收集2和3（即序列第3位和第4位）的和为5，是该区间能收集到的最大和。

数据范围

对于 30% 的数据保证 1 < n < 100，1 < q < 1000；
对于 100% 的数据保证 1 ≤ n,q ≤ 10^6，0 ≤ |ai| ≤ 10^9，1 ≤ l ≤ r ≤ n。