Problem Description

Translated from ROIR 2020 Day2 T4. Плакаты, translator: ksyx.

Your friends have prepared many nice posters to welcome the national team members returning from IOI, and now they only need to work out some details.

To welcome these contestants, your $n$ friends will stand in a circle holding posters. For convenience, they are numbered as friends $1\ldots n$. For $i\in [1,n-1]$, friend $i$ stands next to friend $i+1$, and friend $n$ stands next to friend $1$.

Each poster has a beauty value. The beauty value of the poster held by friend $i$ is $a_i$. When the celebration starts, some friends will raise their posters. For appearance, there must not be $4$ or more consecutive friends raising their posters at the same time.

To make the celebration more interesting, your friends also plan to change posters $q$ times during the celebration. After each change, the beauty value of poster $p_i$ will become $v_i$. Your friends want to know, after each change, the maximum possible sum of beauty values under the rule above.

Your task is: given the initial beauty values, output the maximum sum for the initial state and after each change.

Translator’s note: The statement omits some unnecessary details that are hard to understand.

Input Format

The first line contains an integer $n$, the number of friends.

The next line contains $n$ integers $a_i$, the initial beauty values.

The third line contains an integer $q$, the number of poster changes.

The next $q$ lines each contain two integers $p_i,~v_i$, describing one change.

Output Format

Output $q+1$ lines, representing the maximum sum of beauty values for the initial state and after each change.

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

17
13
15

Hint

Sample 1 Explanation

In the initial state, the best plan is to let friends $2,~4,~5,~6$ raise their posters, and the sum of beauty values is $17$.

After the first change, the beauty value of friend $6$’s poster becomes $0$. In this case, the best plan is to let friends $1,~3,~4,~5$ raise their posters, and the sum is $13$.

After the second change, the beauty value of friend $2$’s poster becomes $5$. In this case, the best plan is to let friends $1,~2,~4,~5$ raise their posters, and the sum is $15$.

Constraints

For $100\%$ of the testdata, $4\le n\le 40000,~0\le a_i,~v_i\le 10^9,~1\le p_i\le n,~0\le q\le 40000$.

The subtasks are as follows:

Translated by ChatGPT 5