题目描述

Joisino即将参加某个编程竞赛的决赛。在这个比赛中，共有$N$个问题，编号为$1$到$N$。Joisino知道她解决第$i$个问题需要$T_i$秒钟。

在这个比赛中，选手首先会选择解决一些问题。然后，选手会解决这些被选中的问题。之后，选手的得分将按照以下方式计算：

• （得分）$\ =\$（对于每对整数$L$和$R$ $(1\leq L\leq R\leq N)$，满足对于每个$i$，$L\leq i\leq R$，问题$i$都被解决的对数）-（选手解决选中问题所需的总时间）

请注意，选手可以选择不解决任何问题，这种情况下得分将为$0$。

另外，比赛给选手提供了$M$种饮料，编号为$1$到$M$。如果Joisino选择饮料$i$（$1\leq i\leq M$），她的大脑将被刺激，她解决问题$P_i$所需的时间将变为$X_i$秒。在这里，$X_i$可能大于原本解决问题$P_i$所需的时间。选择饮料$i$不会影响解决其他问题所需的时间。

选手在比赛开始前只能选择一种饮料。Joisino想知道如果她选择这种饮料，比赛中可以获得的最高分数是多少。你的任务是编写一个程序来计算这个最高分数。

约束条件

• 所有输入值都是整数。
• $1≦N≦3\*10^5$
• $1≦T_i≦10^9$
• （$T_i$的总和）$≦10^{12}$
• $1≦M≦3\*10^5$
• $1≦P_i≦N$
• $1≦X_i≦10^9$

输入

输入从标准输入中以以下格式给出：

$N$ $T_1$ $T_2$ $...$ $T_N$ $M$ $P_1$ $X_1$ $P_2$ $X_2$ $:$ $P_M$ $X_M$

输出

对于每种饮料，按顺序每行打印Joisino选择该饮料时可以获得的最高分数。

示例输入 1

5
1 1 4 1 1
2
3 2
3 10

示例输出 1

9
2

如果Joisino选择饮料$1$，则可以通过解决所有问题获得最高分数。

如果Joisino选择饮料$2$，则可以通过解决问题$1,2,4$和$5$获得最高分数。

示例输入 2

12
1 2 1 3 4 1 2 1 12 3 12 12
10
9 3
11 1
5 35
6 15
12 1
1 9
4 3
10 2
5 1
7 6

示例输出 2

34
35
5
11
35
17
25
26
28
21