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$-ї зміни.

Вхідні дані

$$ \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$
• У будь-який момент кожна монета має додатну вартість.

Вихідні дані

Виведіть $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