Niwango i Nikomoba grają w następującą grę.

W rzędzie ułożono $N$ monet, ponumerowanych od $1$ do $N$. Początkowo monety o nieparzystych numerach są zwrócone orłem do góry, a monety o parzystych numerach — reszką do góry. Wartość monety $i$ wynosi $S_i$.

Gra składa się z $N-1$ tur, ponumerowanych od $1$ do $N-1$. Niwango wykonuje tury o nieparzystych numerach, a Nikomoba — tury o parzystych numerach. W turze $i$ gracz może odwrócić co najwyżej jedną z monet $i$ oraz $i+1$. (Gracz może również nie odwrócić żadnej monety.)

Po $N-1$ turach Niwango zabiera wszystkie monety zwrócone orłem do góry, a Nikomoba — wszystkie monety zwrócone reszką do góry. Wynik gracza jest sumą wartości wszystkich zabranych przez niego monet. Oblicz wynik Niwango, gdy obaj gracze grają optymalnie.

Ponadto nastąpi $Q$ aktualizacji wartości monet. W $i$-tej aktualizacji wartość monety $P_i$ zmniejsza się o $D_i$. Ta aktualizacja pozostaje w mocy przy wszystkich późniejszych aktualizacjach; na przykład po drugiej aktualizacji obowiązują obie pierwsze aktualizacje. Dla każdego $i$ oblicz wynik Niwango przy założeniu, że gracze rozpoczynają grę po $i$-tej aktualizacji.

Wejście

$$ \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$
• W każdej chwili każda moneta ma dodatnią wartość.

Wyjście

Wypisz $Q+1$ wierszy. W $i$-tym wierszu wypisz wynik Niwango, gdy gracze rozpoczynają grę po $(i-1)$ aktualizacjach wartości monet.

Przykład

Wejście 1

4
1 2 3 4
1
4 3

Wyjście 1

7
5

Wejście 2

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

Wyjście 2

19
16
16
12
11
11