問題ヴィジュアル

問題文

横に長い花壇がある. この花壇は一列に $N$ 個の区画に分かれている. 左から $i$ 番目の区画のことを区画 $i$ ということにする.

区画 $i~(1 \leq i \leq N)$ には $A_i$ 本のバラが咲いている. また, 各区画について, バラが $1$ 本以上咲いているとき, そしてその時に限り, その区画は「バラ咲く区画」であるという.

$2$ つの異なる区画 $i$ と区画 $j$ について, $\lvert i - j \rvert = 1$ であるとき, そしてその時に限り, 区画 $i$ と区画 $j$ は隣り合っている.

以下の形式で与えられる $Q$ 個の質問 $q~(1 \leq q \leq Q)$ に答えよ.

• 質問 $q$ : 区画 $X_q$ に咲くバラの数が $B_q$ 本に増加したとする. 区画 $X_q$ から, 隣り合っているバラ咲く区画同士の移動を $0$ 回以上行うことによって到達可能な区画に咲いているバラの本数の合計を求めよ.
  つまり, 以下の問題を解け.

  咲いているバラの数が変化した後における区画 $j$ に咲くバラの本数を $C_j$ とする. このとき, 以下の条件を満たす $1$ 以上 $N$ 以下の整数 $i$ に対する $C_i$ の総和を求めよ.

  • 以下を満たすような長さ $1$ 以上の整数列 $(p_1, p_2, \dots, p_n)$ が存在する.
    • $k = 1, 2, \dots, n$ に対して, $1 \leq p_k \leq N$ である.
    • $p_1=X_q, p_n=i$ である.
    • $k = 1, 2, \dots, (n-1)$ に対して, 区画 $p_k$ と区画 $p_{k+1}$ は隣り合っている. つまり, $\lvert p_k - p_{k+1} \rvert = 1$ である.
    • $k = 1, 2, \dots, n$ に対して, 区画 $p_k$ はバラ咲く区画である. つまり, $C_{p_k} \geq 1$ である.

  ここで, 制約から区画 $X_q$ は必ずバラ咲く区画になることに注意せよ.

なお, $Q$ 個の質問は独立である. つまり, ある問で変化した咲くバラの数の変化は別の問には影響しない.

制約

• $1 \leq N \leq 3 \times 10^5$.
• $0 \leq A_i \lt 10^9 \quad (1 \leq i \leq N)$.
• $1 \leq Q \leq 3 \times 10^5$.
• $1 \leq X_q \leq N \quad (1 \leq q \leq Q)$.
• $A_{X_q} < B_q \leq 10^9 \quad (1 \leq q \leq Q)$.
• 入力は全て整数である.

入力

$N$
$A_1$ $A_2$ $\cdots$ $A_N$
$Q$
$X_1$ $B_1$
$X_2$ $B_2$
$\vdots$
$X_Q$ $B_Q$

出力

出力は $Q$ 行からなる. 第 $q~(1 \leq q \leq Q)$ 行目には質問 $q$ に対する解答を整数で出力せよ.

なお, 入出力が大きくなる場合があるので, 高速な方法で入出力を行うことを推奨する.

サンプル

10
1 0 3 4 5 0 7 0 0 10
3
4 100
2 2
7 7777777

108
15
7777777

2
0 1018
1
1 2023

3041