Problem Description

Takahashi is planning to participate in the Bucket Festival, a competition where various events using buckets are held. Confident in his strength, Takahashi decided to participate in the event called "N Buckets".

The rules of "N Buckets" are as follows:

• Participants form teams of N people, with each team member assigned a number from 1 to N.
• The N team members stand in a circle in clockwise order. Members with consecutive numbers (i and i+1 for 1 ≤ i ≤ N-1, and N and 1) are adjacent.
• Between each pair of adjacent members, a total of N buckets filled with water are placed. The amount of water in each bucket can be decided by the team, but it must be an integer.
• Each team member lifts the two buckets on either side of them. The buckets are lifted by the two members working together. If all N buckets can be lifted, the attempt is successful, and the total amount of water in the buckets is the score.

Takahashi is thinking about how much water to put in each bucket to achieve the highest possible score. First, he measured the strength of each team member, finding that the strength of the i-th member (1 ≤ i ≤ N) is Si. A member with strength p can lift the two buckets if the average amount of water in them is at most p. That is, if the amounts of water in the two buckets are w and v, they can be lifted if (w+v)/2 ≤ p.

Since Takahashi's team is ad-hoc, team members may change. There will be a total of Q changes, and in the i-th change (1 ≤ i ≤ Q), the member numbered Pi will be replaced by a new member with strength Xi. For each member change, determine the maximum score Takahashi's team can achieve immediately after the change.

Input Format

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

$ N $ $ S_1 $ $ S_2 $ ... $ S_N $ $ Q $ $ P_1 $ $ X_1 $ $ P_2 $ $ X_2 $ : $ P_Q $ $ X_Q $

• The first line contains an integer $N\ (3\ ≤\ N\ ≤\ 10^5)$, representing the number of participants. For datasets worth 100 points, $ N $ is guaranteed to be even.
• The second line contains $ N $ integers separated by spaces, where the i-th integer $S_i\ (0\ ≤\ S_i\ ≤\ 10^4)$ represents the strength of the i-th member.
• The third line contains an integer $Q\ (1\ ≤\ Q\ ≤\ 10^5)$, representing the number of member changes.
• The next $ Q $ lines contain the information about the member changes. The i-th line contains two integers $P_i\ (1\ ≤\ P_i\ ≤\ N)$ and $X_i\ (0\ ≤\ X_i\ ≤\ 10^4)$, indicating that in the i-th change, the member numbered $ P_i $ is replaced by a new member with strength $ X_i $.

Output Format

The output consists of $ Q $ lines. The i-th line should contain a single integer representing the maximum score Takahashi's team can achieve immediately after the i-th member change. Ensure a newline at the end of the output.

Sample Input and Output

Sample Input #1

4
2 2 2 2
2
1 3
3 0

Sample Output #1

8
6

Sample Input #2

6
0 0 0 0 0 0
6
3 10000
4 10000
6 10000
2 10000
5 10000
1 10000

Sample Output #2

0
20000
20000
20000
40000
60000

Notes/Hints

Bonus Points

This problem has bonus points:

• If you solve the dataset where $ N $ is odd correctly, you will receive an additional 1 point.

Even if you do not get the bonus point but solve the 100-point dataset correctly, this problem will be considered solved.

Sample Explanation 1

The figure below shows how much water to put in each bucket to achieve the maximum score immediately after each member change. Circles represent members, with the number inside indicating their strength and the number in the top left indicating their number. The number in the bucket illustration represents the amount of water to be put in the bucket.

见题面 Input 部分

见题面 Output 部分