SP1557 GSS2 - Can you answer these queries II

作为一个完美主义者与简单主义者，Yang Zhe 在大部分 OI 题目中都会获得 WA。而且他完全拒绝写两次同类的程序，所以总是在比赛中取得低分。 每次有比赛的时候，Yang Zhe 会先看每道题的分数。对于分数相同的题，他只会做其中的一题。如果运气够好，他可以得到所有想要的分数。 Amber 准备在 SPOJ 举办一场比赛。她已经列出了 $n$ 道候选题目，非常适合 Yang Zhe，因此 Yang Zhe 可以解决任何题目。Amber 将题目排好顺序，开始选择。她将从题目列表中选择一个子段作为最终题目。作为一个有爱心的女孩，她希望选择一个子段（可以为空），让 Yang Zhe 在所有可能的子段中得到最大分数。 Amber 几分钟后就轻松地找到了这个子段。为了增加难度，Amber 决定，Yang Zhe 只有答对她的 $q$ 个问题才能参加这场比赛。问题是：如果最终题目必须是题目列表的区间 $[x,y]$（$1 \le x \le y \le n$）的一个子段，Yang Zhe 能得到的最高分是多少？ 众所周知，Yang Zhe 有点傻（所以他为什么要去做一个负数分值的题？），他又一次获得了 WA……告诉他正确答案吧！

第一行一个正整数 $n \ (n \le 10^5)$。 第二行 $n$ 个整数，表示每道题的分值，保证在区间 $[-10^5,10^5]$ 中。 第三行一个正整数 $q \ (q \le 10^5)$。 第 $3+i$ 行（$1 \le i \le q$）两个正整数 $x,y$，表示第 $i$ 次询问。

输出 $q$ 行，第 $i$ 行一个整数，表示第 $i$ 次询问的答案。