6482: BZOJ2482:[Spoj1557] Can you answer these queries II

Memory Limit:128 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

给定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

加入题单

上一题 下一题 算法标签: