Problem Description

There are $ N + 2 $ plates arranged in a row. These plates are numbered from left to right as plate $ 0 $, plate $ 1 $, ..., plate $ N+1 $. Plates from plate $ 1 $ to plate $ N $ each have some candies on them, while plates $ 0 $ and $ N+1 $ have no candies.

Niwango-kun and Nico Nico TV-chan are trying to divide these candies between them as follows:

1. For each plate from plate $ 1 $ to plate $ N $, move all the candies on that plate to either the plate to the left or the plate to the right. This movement is done simultaneously for all plates after deciding the direction for each plate.
2. Remove all plates that have no candies from the row.
3. Among the remaining plates, Niwango-kun takes the candies on the plates at odd positions from the left ($ 1 $, $ 3 $, $ 5 $, ...), and Nico Nico TV-chan takes the candies on the plates at even positions from the left ($ 2 $, $ 4 $, $ 6 $, ...).

Niwango-kun wants to maximize the number of candies he gets by deciding the direction of candy movement in step $ 1 $. Please write a program to help Niwango-kun.

Initially, plate $ i $ ($ 1 ≦ i ≦ N $) has $ A_i $ candies on it. Then, $ Q $ queries are given to modify the number of candies, which should be processed in order. The $ j $ ($ 1 ≦ j ≦ Q $)th query consists of two integers $ K_j $ and $ X_j $, indicating that the number of candies on plate $ K_j $ should be changed to $ X_j $.

For each $ j $ ($ 1 ≦ j ≦ Q $), output the maximum number of candies Niwango-kun can get when dividing the candies according to the method described above, after processing the first $ j $ queries.

Input Format

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

$ N $ $ A_1 $ $ A_2 $ ... $ A_N $ $ Q $ $ K_1 $ $ X_1 $ : $ K_Q $ $ X_Q $

Output Format

Output $ Q $ lines. The $ j $ ($ 1 ≦ j ≦ Q $)th line should contain the maximum number of candies Niwango-kun can get when dividing the candies after processing the first $ j $ queries.

Sample Input and Output

Sample Input #1

6
3 1 4 1 5 9
1
1 3

Sample Output #1

21

Sample Input #2

5
1 2 3 4 5
1
1 1

Sample Output #2

11

Sample Input #3

8
2 5 2 5 2 5 2 5
5
1 7
6 1
3 6
8 3
2 9

Sample Output #3

27
24
24
22
26

Notes/Hints

Constraints

• $1 ≦ N ≦ 5 \times 10^4$
• $ 1 ≦ A_i ≦ 10^4 $
• $1 ≦ Q ≦ 5 \times 10^4$
• $ 1 ≦ K_j ≦ N $
• $ 1 ≦ X_j ≦ 10^4 $

Partial Points

• If you solve the dataset where $ Q = 1 $, you will be awarded $ 700 $ points.

Sample Explanation 1

This case satisfies the partial point condition. Initially, the number of candies on the plates from left to right is $ 0 $, $ 3 $, $ 1 $, $ 4 $, $ 1 $, $ 5 $, $ 9 $, $ 0 $. If we move the candies on plates $ 1 $ to $ 6 $ to the right, right, left, right, left, and right respectively, the number of candies becomes $ 0 $, $ 0 $, $ 7 $, $ 1 $, $ 5 $, $ 1 $, $ 0 $, $ 9 $. Removing the plates with no candies leaves $ 7 $, $ 1 $, $ 5 $, $ 1 $, $ 9 $, and the total number of candies on the odd-positioned plates from the left is $ 21 $. This is the maximum number of candies Niwango-kun can get in this case.

Sample Explanation 2

This case satisfies the partial point condition.

Sample Explanation 3

This input-output example does not satisfy the partial point condition.

见题面 Input 部分

见题面 Output 部分