给定 个元素的序列。给出 个询问：求 ～ 的最大子段和（可选空子段）。 这个最大子段和有点特殊：一个数字在一段中出现了两次只算一次。 比如：， 出现了 次，但只算一次，于是这个序列的和是 。
第一行一个数 。 第二行 个数，为给定的序列，这些数的绝对值小于等于 。 第三行一个数 。 接下来 行，每行两个数，。
行，每行一个数，为每个询问的答案。
9 4 -2 -2 3 -1 -4 2 2 -6 3 1 2 1 5 4 9
4 5 3
的数据满足：。 的数据满足：。
spoj gss2
