Problem Statement

Chinerist, a math teacher, is planning to set the following problem on a test.

There are $N$ integers $A_i\ (1\le i \le N)$.

You may perform the following operation any number of times.

Operation: Choose an integer $k\ (1\le k\le N)$. Then add $N-2$ to $A_k$ and subtract $1$ from every other element.

The values of $A_i$ may become negative through this operation.

You want to make all $A_i\ (1\le i \le N)$ at most $N-2$ by performing the operation $0$ or more times. It can be proved that this can be achieved in a finite number of operations.

Find the minimum number of operations required.

For the initial values of $N,\ A_i$, the teacher has a set prepared when the problem was given on a past test.

However, reusing them as they are would be bad, so the teacher decided to try changing the values of $A_i$ in various ways.

You are given the integer $N$ and the $N$ integers $A_i\ (1\le i \le N)$ prepared by Chinerist.

$Q$ queries are given, so process all of them.

In each query, $2$ integers $i,\ x\ (1\ \le i \le N)$ are given. Change $A_i$ to $x$, and output the answer to the above problem for the updated $A_i\ (1\le i \le N)$.

Input

$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)$
• All input values are integers.

Output

Output $Q$ lines.

On line $q$, output the answer to the problem for the $q$-th query.

Print a newline at the end.

Sample

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