Niwango and Nikomoba play the following game.

$N$ coins are arranged in a row, and they are numbered $1$ through $N$. Initially, odd-indexed coins are heads up, and even-indexed coins are tails up. The value of the coin $i$ is $S_i$.

The game consists of $N - 1$ turns. The turns are numbered $1$ through $N - 1$. Niwango plays odd-indexed turns, and Nikomoba plays even-indexed turns. In the turn $i$, the player can flip at most one of the coins $i$ and $i + 1$. (The player is allowed not to flip any coins.)

After the $N - 1$ turns, Niwango takes all heads-up coins and Nikomoba takes all tails-up coins. The score of a player is the sum of values of all the coins he takes. Compute Niwango's score when both players play optimally.

Also, there will be $Q$ updates of coin values. In the $i$-th update, the value of coin $P_i$ decreases by $D_i$. This update applies for all later updates; for example, after the second update, both of the first two updates are applied. For each $i$, compute Niwango's score, assuming that they start playing the game after the $i$-th update.

Input

$$ \begin{gathered} N \\ S_1\ \ldots\ S_N \\ Q \\ P_1\ D_1 \\ \vdots \\ P_Q\ D_Q \end{gathered} $$

• $2 \le N \le 200000$
• $1 \le S_i \le 10^9$
• $0 \le Q \le 200000$
• $1 \le P_i \le N$
• $1 \le D_i$
• At any time, each coin has a positive value.

Output

Print $Q + 1$ lines. In the $i$-th line print Niwango's score when they start playing the game after $(i - 1)$ updates of coin values.

Examples

Input 1

4
1 2 3 4
1
4 3

Output 1

7
5

Input 2

8
3 1 4 1 5 9 2 6
5
3 3
6 6
8 4
1 1
6 2

Output 2

19
16
16
12
11
11