题目描述

在一个阳光明媚的日子里，蒜头君和花椰妹在花园里找到了一张藏宝图。这张藏宝图上标记着许多不同的宝藏点，宝藏点上写着一些数字。蒜头君和花椰妹决定一起玩一个游戏，他们会根据藏宝图上给出的线索，从一处宝藏点走到另一处宝藏点，沿途会收集到一些宝藏数字。

他们可以选择收集其中的某些宝藏数字，也可以一个都不收集。他们想知道，如果他们想要自己的收集的宝藏数字之和最多，应该收集哪些宝藏数字呢？

现在，蒜头君和花椰妹需要你的帮助，你能帮他们计算出他们每次冒险能收集的宝藏数字之和的最大值是多少吗？

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

输入格式

第一行一个正整数 $n$，代表序列长度。
第二行 $n$ 个整数，代表序列 $a_1, a_2, \dots, a_n$。
第三行一个正整数 $q$，代表询问组数。
接下来 $q$ 行，每行两个整数 $l, r$，代表一组询问区间的端点。

输出格式

输出 $q$ 行，每行一个整数，表示对应询问的答案。

样例

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

2
4
5

样例解释
序列为 $[2, -1, 2, 3, -5, 2]$，共有 $3$ 组询问：

• 询问区间 $[1,2]$：可选方案中，只收集 $2$ 的和为 $2$，是最大值；
• 询问区间 $[1,3]$：收集第 $1$ 个 $2$ 和第 $3$ 个 $2$，和为 $4$，是最大值；
• 询问区间 $[2,4]$：收集第 $3$ 个 $2$ 和第 $4$ 个 $3$，和为 $5$，是最大值。

数据范围

• 对于 $30\%$ 的数据：$1 < n < 100$，$1 < q < 1000$；
• 对于 $100\%$ 的数据：$1 \le n, q \le 10^6$，$0 \le |a_i| \le 10^9$，$1 \le l \le r \le n$。