Niwango và Nikomoba chơi trò chơi sau.

Có $N$ đồng xu được xếp thành một hàng và đánh số từ $1$ đến $N$. Ban đầu, các đồng xu có chỉ số lẻ ngửa mặt trước, còn các đồng xu có chỉ số chẵn ngửa mặt sau. Giá trị của đồng xu $i$ là $S_i$.

Trò chơi gồm $N-1$ lượt, được đánh số từ $1$ đến $N-1$. Niwango chơi các lượt có chỉ số lẻ, còn Nikomoba chơi các lượt có chỉ số chẵn. Ở lượt $i$, người chơi có thể lật nhiều nhất một trong hai đồng xu $i$ và $i+1$. (Người chơi được phép không lật đồng xu nào.)

Sau $N-1$ lượt, Niwango lấy tất cả các đồng xu ngửa mặt trước, còn Nikomoba lấy tất cả các đồng xu ngửa mặt sau. Điểm của một người chơi là tổng giá trị của tất cả các đồng xu mà người đó lấy. Hãy tính điểm của Niwango khi cả hai người chơi đều chơi tối ưu.

Ngoài ra, sẽ có $Q$ lần cập nhật giá trị đồng xu. Trong lần cập nhật thứ $i$, giá trị của đồng xu $P_i$ giảm đi $D_i$. Lần cập nhật này vẫn có hiệu lực trong tất cả các lần cập nhật sau; ví dụ, sau lần cập nhật thứ hai, cả hai lần cập nhật đầu tiên đều được áp dụng. Với mỗi $i$, hãy tính điểm của Niwango, giả sử họ bắt đầu chơi sau lần cập nhật thứ $i$.

Dữ liệu vào

$$ \begin{array}{l} N \\ S_1\ \ldots\ S_N \\ Q \\ P_1\ D_1 \\ \vdots \\ P_Q\ D_Q \end{array} $$

• $2 \le N \le 200000$.
• $1 \le S_i \le 10^9$.
• $0 \le Q \le 200000$.
• $1 \le P_i \le N$.
• $1 \le D_i$.
• Tại mọi thời điểm, mỗi đồng xu đều có giá trị dương.

Dữ liệu ra

In ra $Q+1$ dòng. Ở dòng thứ $i$, in điểm của Niwango khi họ bắt đầu chơi sau $(i-1)$ lần cập nhật giá trị đồng xu.

Ví dụ

Dữ liệu vào 1

4
1 2 3 4
1
4 3

Dữ liệu ra 1

7
5

Dữ liệu vào 2

8
3 1 4 1 5 9 2 6
5
3 3
6 6
8 4
1 1
6 2

Dữ liệu ra 2

19
16
16
12
11
11