题目描述

给定 $n$ 个元素的序列。给出 $m$ 个询问：求 $l_i ～ r_i$ 的最大子段和（可选空子段）。
这个最大子段和有点特殊：一个数字在一段中出现了两次只算一次。
比如：$1,2,3,2,2$，$2$ 出现了 $3$ 次，但只算一次，于是这个序列的和是 $1+2+3=6$。

输入格式

第一行一个数 $n$。
第二行 $n$ 个数，为给定的序列，这些数的绝对值小于等于 $1 \times 10^5$。
第三行一个数 $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 1 \times 10^5$。

题目来源

spoj gss2