[Spoj1557] Can you answer these queries II

给定一个包含 $n$ 个元素的序列。

有 $m$ 次询问。对于第 $i$ 次询问，需要求出区间 $[l_i,r_i]$ 内的最大子段和，允许选择空子段。

子段和的计算方式较为特殊：同一个数在所选子段中无论出现多少次，都只计算一次。例如，子段 $1,2,3,2,2,2$ 中，数 $2$ 虽然出现了多次，但只计算一次，因此该子段的和为 $1+2+3=6$。

输入格式

第一行包含一个整数 $n$。

第二行包含 $n$ 个整数，表示给定的序列。

第三行包含一个整数 $m$。

接下来 $m$ 行，每行包含两个整数 $l_i,r_i$，表示一次询问的区间。

输出格式

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

样例输入

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

样例输出

4
5
3

数据范围

• 对于 $30\%$ 的数据，$1\le n,m\le 100$；
• 对于 $100\%$ 的数据，$1\le n,m\le 10^5$；
• 序列中每个元素的绝对值不超过 $10^5$。

来源与许可

本题为 SPOJ 1557「Can you answer these queries II」，题面与测试数据整理自 BZOJ 2482。

样例 1

输入

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

输出

4
5
3