Niwango et Nikomoba jouent au jeu suivant.

$N$ pièces sont disposées en ligne et numérotées de $1$ à $N$. Initialement, les pièces d'indice impair montrent leur face, et celles d'indice pair montrent leur pile. La valeur de la pièce $i$ est $S_i$.

Le jeu comprend $N-1$ tours, numérotés de $1$ à $N-1$. Niwango joue aux tours d'indice impair, et Nikomoba aux tours d'indice pair. Au tour $i$, le joueur peut retourner au plus une des pièces $i$ et $i+1$. (Il est autorisé à ne retourner aucune pièce.)

Après les $N-1$ tours, Niwango prend toutes les pièces montrant leur face et Nikomoba prend toutes les pièces montrant leur pile. Le score d'un joueur est la somme des valeurs de toutes les pièces qu'il prend. Calculez le score de Niwango lorsque les deux joueurs jouent de manière optimale.

Il y aura également $Q$ mises à jour des valeurs des pièces. Lors de la $i$-ième mise à jour, la valeur de la pièce $P_i$ diminue de $D_i$. Cette mise à jour reste appliquée lors de toutes les mises à jour ultérieures ; par exemple, après la deuxième mise à jour, les deux premières mises à jour sont appliquées. Pour chaque $i$, calculez le score de Niwango en supposant que les joueurs commencent la partie après la $i$-ième mise à jour.

Entrée

$$ \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$
• À tout moment, chaque pièce a une valeur strictement positive.

Sortie

Affichez $Q+1$ lignes. Sur la $i$-ième ligne, affichez le score de Niwango lorsque les joueurs commencent la partie après $i-1$ mises à jour des valeurs des pièces.

Exemples

Entrée 1

4
1 2 3 4
1
4 3

Sortie 1

7
5

Entrée 2

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

Sortie 2

19
16
16
12
11
11