Niwango und Nikomoba spielen das folgende Spiel.

$N$ Münzen liegen in einer Reihe und sind von $1$ bis $N$ nummeriert. Anfangs zeigen Münzen mit ungeradem Index die Kopfseite und Münzen mit geradem Index die Zahlseite. Der Wert der Münze $i$ ist $S_i$.

Das Spiel besteht aus $N - 1$ Zügen. Die Züge sind von $1$ bis $N - 1$ nummeriert. Niwango spielt die Züge mit ungeradem Index und Nikomoba die mit geradem Index. Im Zug $i$ darf der Spieler höchstens eine der Münzen $i$ und $i + 1$ umdrehen. (Der Spieler darf auch keine Münze umdrehen.)

Nach den $N - 1$ Zügen nimmt Niwango alle Münzen, deren Kopfseite oben liegt, und Nikomoba alle Münzen, deren Zahlseite oben liegt. Die Punktzahl eines Spielers ist die Summe der Werte aller Münzen, die er nimmt. Berechne Niwangos Punktzahl, wenn beide Spieler optimal spielen.

Außerdem gibt es $Q$ Änderungen der Münzwerte. Bei der $i$-ten Änderung wird der Wert der Münze $P_i$ um $D_i$ verringert. Diese Änderung bleibt auch bei allen späteren Änderungen wirksam; beispielsweise sind nach der zweiten Änderung beide ersten Änderungen angewendet. Berechne für jedes $i$ Niwangos Punktzahl unter der Annahme, dass sie das Spiel nach der $i$-ten Änderung beginnen.

Eingabe

$$ \begin{gathered} N\\ S_1\quad\ldots\quad S_N\\ Q\\ P_1\quad D_1\\ \vdots\\ P_Q\quad 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$
• Zu jedem Zeitpunkt hat jede Münze einen positiven Wert.

Ausgabe

Gib $Q + 1$ Zeilen aus. Gib in der $i$-ten Zeile Niwangos Punktzahl aus, wenn sie das Spiel nach $i - 1$ Änderungen der Münzwerte beginnen.

Beispiele

Eingabe 1

4
1 2 3 4
1
4 3

Ausgabe 1

7
5

Eingabe 2

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

Ausgabe 2

19
16
16
12
11
11