题目描述

joisinoお姉ちゃんは、あるプログラミングコンテストの決勝を控えています。 このコンテストでは、$N$ 問の問題が用意されており、それらには $1～N$ の番号がついています。 joisinoお姉ちゃんは、問題 $i(1≦i≦N)$ を解くのにかかる時間が $T_i$ 秒であることを知っています。

このコンテストでは、コンテスタントはまず最初に、これから解く問題をいくつか選びます。 次にそれらの問題を解き、すべて解き終わると、スコアの計算が行われます。 このコンテストでのスコアの計算方法は特殊であり、具体的には、以下の式で計算されます。

• スコア $=$ 「整数の組 $L,R(1≦L≦R≦N)$ であって、$L≦i≦R$ を満たす全ての $i$ について、問題 $i$ が解かれているようなもの」の個数 $ー$ 問題を解くのに要した時間の合計

なお、問題を $1$ つも解かないことも許され、その際のスコアは $0$ になります。

また、このコンテストでは、$M$ 種類のドリンクが提供されており、$1～M$ の番号がついています。 そして、ドリンク $i(1≦i≦M)$ を飲むと、脳が刺激され、問題 $P_i$ を解くのにかかる時間が $X_i$ 秒になります。 なお、$X_i$ が、もともと問題 $P_i$ を解くのに要する時間より長いこともありえます。 他の問題を解くのにかかる時間に変化はありません。

コンテスタントは、コンテスト開始前にいずれかのドリンクを $1$ 本だけ飲むことができます。 そこでjoisinoお姉ちゃんは、それぞれのドリンクについて、それを飲んだ際に、コンテストで取ることのできる最大スコアを知りたいと思いました。 あなたの仕事は、joisinoお姉ちゃんの代わりにこれを求めるプログラムを作成することです。

输入格式

入力は以下の形式で標準入力から与えられる。

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

输出格式

それぞれのドリンクについて、それを飲んだ際の最大スコアを求め、順番に $1$ 行ずつ出力せよ。

题目大意

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$ 。

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

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

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

感谢@OrangeLee 提供的翻译

5
1 1 4 1 1
2
3 2
3 10

9
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

34
35
5
11
35
17
25
26
28
21

提示

制約

• 入力は全て整数である
• $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$

Sample Explanation 1

$1$ 番目のドリンクを飲んだ場合、全ての問題を解くことで最大スコアが得られます。 $2$ 番目のドリンクを飲んだ場合、$1,2,4,5$ 番目の問題を解くことで最大スコアが得られます。