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