Niwango dan Nikomoba memainkan permainan berikut.

Sebanyak $N$ koin disusun dalam satu baris dan diberi nomor dari $1$ hingga $N$. Pada awalnya, koin bernomor ganjil menghadap sisi kepala ke atas, sedangkan koin bernomor genap menghadap sisi ekor ke atas. Nilai koin $i$ adalah $S_i$.

Permainan terdiri atas $N-1$ giliran. Giliran diberi nomor dari $1$ hingga $N-1$. Niwango bermain pada giliran bernomor ganjil, sedangkan Nikomoba bermain pada giliran bernomor genap. Pada giliran $i$, pemain dapat membalik paling banyak satu dari koin $i$ dan $i+1$. (Pemain diperbolehkan untuk tidak membalik koin apa pun.)

Setelah $N-1$ giliran, Niwango mengambil semua koin yang sisi kepalanya menghadap ke atas dan Nikomoba mengambil semua koin yang sisi ekornya menghadap ke atas. Skor seorang pemain adalah jumlah nilai semua koin yang diambilnya. Hitung skor Niwango ketika kedua pemain bermain secara optimal.

Selain itu, akan ada $Q$ pembaruan nilai koin. Pada pembaruan ke-$i$, nilai koin $P_i$ berkurang sebesar $D_i$. Pembaruan ini tetap berlaku pada semua pembaruan berikutnya; misalnya, setelah pembaruan kedua, kedua pembaruan pertama telah diterapkan. Untuk setiap $i$, hitung skor Niwango dengan asumsi mereka mulai memainkan permainan setelah pembaruan ke-$i$.

Masukan

$$ \begin{matrix} N \\ S_1\ \ldots\ S_N \\ Q \\ P_1\ D_1 \\ \vdots \\ P_Q\ D_Q \end{matrix} $$

• $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$
• Pada setiap saat, setiap koin memiliki nilai positif.

Keluaran

Cetak $Q+1$ baris. Pada baris ke-$i$, cetak skor Niwango ketika mereka mulai memainkan permainan setelah $(i-1)$ pembaruan nilai koin.

Contoh

Masukan 1

4
1 2 3 4
1
4 3

Keluaran 1

7
5

Masukan 2

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

Keluaran 2

19
16
16
12
11
11