题目描述

Joisino 要去打 final。这场比赛有 $N$ 道题，编号从 $1$ 到 $N$。Joisino 做第 $i$ 道题花费的时间为 $T_i$。

这场比赛中，选手的做题方式是选择自己想做的题来做，并且一定能做出来。最后，选手的得分将以如下方式计算：

得分 $=$ 满足条件的二元组 $(l,r)$ 的个数 $-$ 解决选了的题所花费的时间；

其中，二元组 $(l,r)$ 需要满足的条件是：对于所有满足 $l\le i\le r$ 的 $i$，第 $i$ 题都做了。另外，$l$ 和 $r$ 还需满足 $1\le l\le r\le N$。

注意，Joisino 可以选择对所有题弃疗，这样她将爆零。

主办方为参赛者提供了 $M$ 种饮料，从 $1$ 标号至 $M$。如果 Joisino 喝了第 $i$ 种饮料，她做第 $P_i$ 题时会兴奋，做第 $P_i$ 题的时间将从 $T_{P_i}$ 变成 $X_i$，注意 $X_i$ 不一定比 $T_{P_i}$ 小；做其它题的时间不受影响。

一位参赛者能且仅能带一种饮料进入考场。Joisino 想知道如果她喝下了每种饮料，他的最大得分。

输入格式

第一行一个整数 $N(1\le N\le 3\times 10^5)$。
第二行 $N$ 个整数 $T_1,T_2,\cdots,T_N(1\le T_i\le 10^9)$。
第三行一个整数 $M(1\le M\le 3\times 10^5)$。
接下来 $M$ 行，第 $i$ 行两个整数 $P_i,X_i,(1\le P_i\le N,1\le X_i\le 10^9)$。

保证单个测试点中 $\sum\limits_{i=1}^n T_i\le 10^{12}$。

输出格式

输出 $M$ 行，第 $i$ 行一个整数表示喝下第 $i$ 种饮料后参赛可以获得的最大得分。

输入输出样例 #1

输入 #1

5
1 1 4 1 1
2
3 2
3 10

输出 #1

9
2

输入输出样例 #2

输入 #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

说明/提示

样例 1 解释

如果 Joisino 喝下了第一种饮料，她可以通过完成全部题目获得最大得分。

如果 Joisino 喝下了第二种饮料，她可以通过完成题目 $1,2,4,5$ 获得最大得分。