Niwango y Nikomoba juegan al siguiente juego.

Hay $N$ monedas dispuestas en una fila, numeradas del $1$ al $N$. Inicialmente, las monedas con índice impar tienen la cara hacia arriba y las de índice par tienen la cruz hacia arriba. El valor de la moneda $i$ es $S_i$.

El juego consta de $N-1$ turnos, numerados del $1$ al $N-1$. Niwango juega en los turnos con índice impar y Nikomoba en los de índice par. En el turno $i$, el jugador puede dar la vuelta, como máximo, a una de las monedas $i$ e $i+1$. (Está permitido no dar la vuelta a ninguna moneda.)

Después de los $N-1$ turnos, Niwango se queda con todas las monedas que tienen la cara hacia arriba y Nikomoba con todas las que tienen la cruz hacia arriba. La puntuación de un jugador es la suma de los valores de todas las monedas que recibe. Calcula la puntuación de Niwango cuando ambos jugadores juegan de forma óptima.

Además, habrá $Q$ actualizaciones de los valores de las monedas. En la actualización $i$, el valor de la moneda $P_i$ disminuye en $D_i$. Esta actualización se mantiene en todas las actualizaciones posteriores; por ejemplo, después de la segunda actualización, se aplican las dos primeras actualizaciones. Para cada $i$, calcula la puntuación de Niwango suponiendo que empiezan a jugar después de la actualización $i$.

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$
• En todo momento, cada moneda tiene un valor positivo.

Salida

Imprime $Q+1$ líneas. En la línea $i$, imprime la puntuación de Niwango cuando empiezan a jugar después de $(i-1)$ actualizaciones de los valores de las monedas.

Ejemplos

Entrada 1

4
1 2 3 4
1
4 3

Salida 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

Salida 2

19
16
16
12
11
11