Problem Description

Niwango and Nikomoba are playing a game with coins.

Initially, there are $ N $ coins arranged in a row, numbered from $ 1 $ to $ N $ from left to right. The coins with odd numbers are face up, and those with even numbers are face down. The value of coin $ i $ is $ S_i $.

The game consists of $ N-1 $ turns, with Niwango playing on odd-numbered turns and Nikomoba playing on even-numbered turns. On turn $ i $, the player can flip either coin $ i $ or coin $ i+1 $. If they do not want to flip either, they can choose not to flip any coin.

After $ N-1 $ turns, Niwango collects the coins that are face up, and Nikomoba collects the coins that are face down. The score of each player is the sum of the values of the coins they collect. What will be Niwango's score? Both players are very smart and will always play optimally to maximize their scores.

Before the game starts, Nikomoba may have drawn on some coins, reducing their values. Nikomoba drew a total of $ Q $ times, and the $ i $-th drawing reduced the value of coin $ P_i $ by $ D_i $.

For each of the $ Q $ drawings, calculate Niwango's score if the game starts immediately after the drawing.

Input Format

The input is given from the standard input in the following format:

$ N $ $ S_1 $ $ S_2 $ ... $ S_N $ $ Q $ $ P_1 $ $ D_1 $ $ P_2 $ $ D_2 $ : $ P_Q $ $ D_Q $

• The first line contains an integer $N\ (2\ ≦\ N\ ≦\ 200,000)$, representing the number of coins.
• The second line contains $ N $ integers separated by spaces, where the $ i $-th integer $S_i\ (1\ ≦\ S_i\ ≦\ 10^9)$ represents the initial value of coin $ i $.
• The third line contains an integer $Q\ (0\ ≦\ Q\ ≦\ 200,000)$, representing the number of drawings.
• The next $ Q $ lines contain two integers each, $P_i\ (1\ ≦\ P_i\ ≦\ N)$ and $D_i\ (1\ ≦\ D_i)$, separated by spaces, indicating that the $ i $-th drawing reduced the value of coin $ P_i $ by $ D_i $. The value of each coin is always guaranteed to be at least $ 1 $.

Output Format

The output consists of $ Q+1 $ lines. The first line should contain Niwango's score if the game starts from the initial state, and from the second line to the $ Q+1 $-th line, the $ i $-th line should contain Niwango's score if the game starts immediately after the $ i $-th drawing. Ensure to include a newline at the end of the output.

Sample Input and Output

Sample Input #1

4
1 2 3 4
1
4 3

Sample Output #1

7
5

Sample Input #2

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

Sample Output #2

19
16
16
12
11
11

Notes/Hints

Partial Points

This problem has partial points.

• If you solve dataset 1 with $Q\ =\ 0$, you will be awarded $ 10 $ points.
• If you solve dataset 2 with $S_i\ ≦\ 25$, you will be awarded an additional $ 80 $ points.
• If you solve all test cases, you will be awarded an additional $ 90 $ points.

Sample Explanation 1

In this example, there are $ 4 $ coins with values $ 1, 2, 3, 4 $ from left to right. Initially, the coins are face up, face down, face up, face down. Starting the game from this state, - Niwango flips coin $ 2 $ → Nikomoba flips coin $ 3 $ → Niwango flips coin $ 4 $ resulting in the final state face up, face up, face down, face up, so Niwango's score is $ 7 $. Also, there is $ 1 $ query, which reduces the value of coin $ 4 $ to $ 1 $. Starting the game from this state, - Niwango flips coin $ 2 $ → Nikomoba flips coin $ 2 $ → Niwango flips coin $ 4 $ resulting in the final state face up, face down, face up, face up, so Niwango's score is $ 5 $.

见题面 Input 部分

见题面 Output 部分