[Spoj1557] Can you answer these queries II
时间限制：20s 空间限制：128MB
题目描述
给定n个元素的序列。
给出m个询问：求l[i]~r[i]的最大子段和（可选空子段）。
这个最大子段和有点特殊：一个数字在一段中出现了两次只算一次。
比如：1，2，3，2，2，2出现了3次，但只算一次，于是这个序列的和是1+2+3=6。
输入格式
第一行一个数n。
第二行n个数，为给定的序列，这些数的绝对值小于等于100000。
第三行一个数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 <= n, m <= 100
100%：1 <= n, m <= 100000
题目来源
spoj gss2