AT_arc066_d.[ARC066F] Contest with Drinks Hard

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 解释

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

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

Translated by @UnnamedOrange，Updated by @chenxi2009