Niwango и Nikomoba играют в следующую игру.

В ряд расположены $N$ монет, пронумерованных от $1$ до $N$. Изначально монеты с нечётными номерами лежат орлом вверх, а монеты с чётными номерами — решкой вверх. Стоимость монеты $i$ равна $S_i$.

Игра состоит из $N-1$ ходов. Ходы пронумерованы от $1$ до $N-1$. Niwango делает ходы с нечётными номерами, а Nikomoba — с чётными. На ходу $i$ игрок может перевернуть не более одной из монет $i$ и $i+1$. (Игроку разрешается не переворачивать ни одной монеты.)

После $N-1$ ходов Niwango забирает все монеты, лежащие орлом вверх, а Nikomoba — все монеты, лежащие решкой вверх. Счёт игрока равен сумме стоимостей всех забранных им монет. Вычислите счёт Niwango, если оба игрока играют оптимально.

Также произойдёт $Q$ изменений стоимости монет. При $i$-м изменении стоимость монеты $P_i$ уменьшается на $D_i$. Это изменение сохраняется при всех последующих изменениях: например, после второго изменения действуют оба первых изменения. Для каждого $i$ вычислите счёт Niwango, предполагая, что игроки начинают игру после $i$-го изменения.

Входные данные

$$ 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$.
• В любой момент стоимость каждой монеты положительна.

Выходные данные

Выведите $Q+1$ строку. В $i$-й строке выведите счёт Niwango, если игроки начинают игру после $(i-1)$ изменений стоимости монет.

Примеры

Входные данные 1

4
1 2 3 4
1
4 3

Выходные данные 1

7
5

Входные данные 2

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

Выходные данные 2

19
16
16
12
11
11