Niwango e Nikomoba jogam o seguinte jogo.

Há $N$ moedas dispostas numa fila, numeradas de $1$ a $N$. Inicialmente, as moedas de índice ímpar estão com a cara para cima, e as de índice par estão com a coroa para cima. O valor da moeda $i$ é $S_i$.

O jogo consiste em $N-1$ turnos. Os turnos são numerados de $1$ a $N-1$. Niwango joga nos turnos de índice ímpar, e Nikomoba joga nos turnos de índice par. No turno $i$, o jogador pode virar, no máximo, uma das moedas $i$ e $i+1$. (É permitido não virar nenhuma moeda.)

Após os $N-1$ turnos, Niwango fica com todas as moedas com a cara para cima e Nikomoba fica com todas as moedas com a coroa para cima. A pontuação de um jogador é a soma dos valores de todas as moedas que recebe. Calcule a pontuação de Niwango quando ambos os jogadores jogam de forma ótima.

Além disso, haverá $Q$ atualizações dos valores das moedas. Na $i$-ésima atualização, o valor da moeda $P_i$ diminui em $D_i$. Esta atualização mantém-se em todas as atualizações posteriores; por exemplo, após a segunda atualização, ambas as primeiras duas atualizações estão aplicadas. Para cada $i$, calcule a pontuação de Niwango, supondo que começam a jogar após a $i$-ésima atualização.

Entrada

$N$

$S_1\ \ldots\ S_N$

$Q$

$P_1\ D_1$

$\vdots$

$P_Q\ D_Q$

• $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$
• Em qualquer momento, cada moeda tem um valor positivo.

Saída

Imprima $Q+1$ linhas. Na $i$-ésima linha, imprima a pontuação de Niwango quando começam a jogar após $(i-1)$ atualizações dos valores das moedas.

Exemplos

Entrada 1

4
1 2 3 4
1
4 3

Saída 1

7
5

Entrada 2

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

Saída 2

19
16
16
12
11
11