포스터

친구들은 국제 정보 올림피아드를 마치고 돌아오는 국가대표팀을 맞이할 준비를 하고 있다. 이를 위해 여러 장의 화려한 포스터를 준비했다. 이제 축하의 세부 사항만 정하면 된다.

팀을 맞이하기 위해 $n$명의 친구가 원을 이루어 선다. 원을 따라 위치한 순서대로 1번부터 $n$번까지 번호를 붙이자. 그러면 모든 $i$에 대해 $1 \le i \le n-1$인 경우 $i$번과 $i+1$번 친구가 서로 옆에 서 있고, $n$번과 1번 친구도 서로 옆에 서 있다. 친구들은 각자 포스터를 하나씩 가지고 있다. 각 포스터는 화려함이라는 음이 아닌 정수로 나타낼 수 있다. $i$번 친구의 포스터는 화려함 $a_i$를 가진다.

축하가 시작되면 일부 친구가 포스터를 들어 팀에게 보여준다. 팀원들이 헷갈리지 않고 모든 포스터를 볼 수 있도록, 포스터를 든 친구가 넷 이상 연속으로 서 있으면 안 된다.

친구들은 만나는 동안 포스터를 바꿀 계획이다. 모두 $q$번의 변경이 이루어진다. $i$번째 변경 후에 $p_i$번 친구의 포스터는 화려함 $v_i$를 가진다. 친구들은 각 변경 후에 정해진 제약을 어기지 않으면서 들 수 있는 포스터의 최대 총 화려함을 알고 싶어 한다.

포스터의 초기 화려함과 변경 순서가 주어질 때, 처음과 각 변경 후에 연속으로 세 장 이하의 포스터만 들 수 있다는 조건을 어기지 않으면서 얻을 수 있는 든 포스터의 최대 총 화려함을 구하는 프로그램을 작성해야 한다.

첫째 줄에는 정수 $n$ ($4 \le n \le 40\,000$)이 주어진다. 이는 친구의 수이다.

둘째 줄에는 $n$개의 정수 $a_i$ ($0 \le a_i \le 10^9$)가 주어진다. 이는 친구들의 포스터 화려함의 초깃값이다.

셋째 줄에는 하나의 정수 $q$ ($0 \le q \le 40\,000$)가 주어진다. 이는 친구들이 수행한 포스터 변경의 수이다.

다음 $q$개의 줄 각각에는 두 정수 $p_i$와 $v_i$ ($1 \le p_i \le n$; $0 \le v_i \le 10^9$)가 주어진다. 이는 포스터가 바뀐 친구의 번호와 그 포스터의 새 화려함이다.

$q+1$개의 수를 출력한다. 첫 번째 변경 전과 각 포스터 변경 후에, 연속으로 세 장을 초과하여 들 수 없다는 조건 아래에서 든 포스터의 최대 총 화려함을 하나의 정수로 출력한다.

예제의 테스트를 살펴보자.

첫 번째 변경 전에는 2, 4, 5, 6번 친구가 포스터를 들어야 한다. 든 포스터의 총 화려함은 17이 된다.

첫 번째 변경 후 6번 친구의 포스터 화려함은 0이 된다. 이제는 1, 3, 4, 5번 친구가 포스터를 들어야 한다. 총 화려함은 13이 된다.

두 번째 변경 후 2번 친구의 포스터 화려함은 5가 된다. 1, 2, 4, 5번 친구가 포스터를 들어야 한다. 총 화려함은 15가 된다.