問題文

数学教師の chinerist 先生は次の問題をテストで出題しようと考えています。

$N$ 個の整数 $A_i\ (1\le i \le N)$ があります。

あなたは以下の操作を好きな回数行えます。

操作: 整数 $k\ (1\le k\le N)$ を選ぶ。そのあと $A_k$ に $N-2$ を足し、それ以外の要素から $1$ を引く

この操作によって $A_i$ の値が負になってもかまいません。

操作を $0$ 回以上行うことですべての $A_i\ (1\le i \le N)$ が $N-2$ 以下になるようにしたいです。これは有限回の操作で達成できることが証明できます。

必要な操作の最小回数を求めてください。

はじめに与える $N,\ A_i$ は、過去のテストで出題したときに用意したものがあります。

しかし、そのまま出すのはまずいので $A_i$ の値をいろいろ変えてみることにしました。

chinerist 先生が用意していた整数 $N$ と $N$ 個の整数 $A_i\ (1\le i \le N)$ が与えられます。

$Q$ 個のクエリが与えられるのですべて処理してください。

各クエリでは $2$ つの整数 $i,\ x\ (1\ \le i \le N)$ が与えられるので $A_i$ を $x$ に変更し、変更後の $A_i\ (1\le i \le N)$ に対する上の問題の答えを出力してください。

入力

$N$
$A_1\ A_2\ \dots\ A_N$
$Q$
$i_1\ x_1$
$\vdots$
$i_Q\ x_Q$

• $1\le N\le 2\times 10^5$
• $0\le A_i\le 10^9\ (1\le i\le N)$
• $1\le Q\le 10^5$
• $1\le i_q\le N\ (1\le q \le Q)$
• $0\le x_q\le 10^9\ (1\le q\ \le Q)$
• 与えられる入力はすべて整数

出力

$Q$ 行出力してください。

$q$ 行目には $q$ 番目のクエリでの問題の答えを出力してください。

最後に改行してください。

サンプル

3
1 2 3
1
1 1

4

5
3 3 3 3 3
2
3 3
2 10

0
8

15
8 45 47 41 32 31 13 28 46 21 8 8 26 47 15
5
8 41
4 45
1 34
14 25
8 8

303
303
331
317
275