Posters

A group of friends is getting ready to welcome the national team returning from the International Olympiad in Informatics. They have prepared many colorful posters. Only the details of the celebration remain to be worked out.

To greet the team, $n$ friends stand in a circle. Number them from 1 to $n$ in the order they are arranged around the circle. Then for every $i$ with $1 \le i \le n-1$, friends $i$ and $i+1$ stand next to each other, and friends $n$ and 1 also stand next to each other. Each friend has a poster. Each poster is described by its colorfulness, a non-negative integer. The poster of friend $i$ has colorfulness $a_i$.

When the celebration begins, some of the friends raise their posters and show them to the team. So that the team members do not get confused and can see all the posters, there must not be four or more consecutive friends holding up a poster.

The friends plan to change posters during the meeting. In total $q$ changes will be made. After the $i$-th change, the poster of friend $p_i$ has colorfulness $v_i$. After each change, the friends want to determine the maximum total colorfulness of the raised posters they can achieve without violating the restriction.

You must write a program that, given the initial colorfulness of the posters and the sequence of changes, determines at the start and after each change the maximum total colorfulness of the raised posters that can be achieved without violating the condition that no more than three posters in a row are raised.

The first line of input contains the integer $n$ ($4 \le n \le 40\,000$), the number of friends.

The second line contains $n$ integers $a_i$ ($0 \le a_i \le 10^9$), the initial colorfulness values of the friends' posters.

The third line contains a single integer $q$ ($0 \le q \le 40\,000$), the number of poster changes the friends made.

Each of the following $q$ lines contains two integers $p_i$ and $v_i$ ($1 \le p_i \le n$; $0 \le v_i \le 10^9$), the number of the friend whose poster changed and the new colorfulness of that poster.

Output $q+1$ numbers. Before the first change and after each poster change, output a single integer: the maximum total colorfulness of the raised posters under the condition that no more than three posters in a row may be raised.

Consider the test from the sample.

Before the first change, friends 2, 4, 5, 6 should raise their posters. The total colorfulness of the raised posters is 17.

After the first change, the poster of friend 6 has colorfulness 0. Now friends 1, 3, 4, 5 should raise their posters. The total colorfulness is 13.

After the second change, the poster of friend 2 has colorfulness 5. Friends 1, 2, 4, 5 should raise their posters. The total colorfulness is 15.