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