يلعب 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