配点 : $1400$ 点

問題文

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

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

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

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

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

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

制約

• 入力は全て整数である
• $1 \leq N \leq 3*10^5$
• $1 \leq T_i \leq 10^9$
• $T_i$ の総和 $\leq 10^{12}$
• $1 \leq M \leq 3*10^5$
• $1 \leq P_i \leq N$
• $1 \leq X_i \leq 10^9$

入力

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

$N$

$T_1$ $T_2$ $...$ $T_N$

$M$

$P_1$ $X_1$

$P_2$ $X_2$

$:$

$P_M$ $X_M$

出力

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

5
1 1 4 1 1
2
3 2
3 10

9
2

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

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

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