问题描述

有 $N + 2$ 个盘子排成一行。将这些盘子从左到右编号为盘子 $0$, 盘子 $1$, ..., 盘子 $N+1$。盘子 $1$ 到盘子 $N$ 中每个盘子上都放有一些糖果，盘子 $0$ 和盘子 $N+1$ 上没有放糖果。

尼万哥君和尼可尼科电视酱想要按照以下方式分享这些糖果:

1. 对于盘子 $1$ 到盘子 $N$ 中的每个盘子，将该盘子上的所有糖果移动到左边或右边的相邻盘子上。此次移动是在确定每个盘子的左或右方向后同时进行的。
2. 将没有糖果的盘子从排列中移除。
3. 在剩下的盘子中，尼万哥君将拿走左起奇数编号($1$, $3$, $5$, ... 号) 的盘子上的糖果，尼可尼科电视酱将拿走左起偶数编号($2$, $4$, $6$, ... 号) 的盘子上的糖果。

尼万哥君希望在步骤 $1$ 中决定移动糖果的方向时，能尽可能多地获得糖果。请为尼万哥君设计以下程序。

初始时，假设盘子 $i$ ($1 ≦ i ≦ N$) 上有 $A_i$ 个糖果。然后给出 $Q$ 个查询来改变糖果数量，请按顺序处理这些查询。第 $j$ ($1 ≦ j ≦ Q$) 个查询由两个整数 $K_j$ 和 $X_j$ 组成，表示将盘子 $K_j$ 上的糖果数量改为 $X_j$。

对于每个 $j$ ($1 ≦ j ≦ Q$)，请输出在处理 $j$ 个查询之前的状态下，尼万哥君和尼可尼科电视酱按照上述方法分配糖果时，尼万哥君能够获得的最大糖果数。

约束条件

• $1≦N≦5 \\times 10^4$
• $1≦A_i≦10^4$
• $1≦Q≦5 \\times 10^4$
• $1≦K_j≦N$
• $1≦X_j≦10^4$

部分得分

• 如果满足 $Q=1$ 的数据集，则可获得 $700$ 分。

输入

输入从标准输入中以以下格式给出。

$N$ $A_1$ $A_2$ ... $A_N$ $Q$ $K_1$ $X_1$ : $K_Q$ $X_Q$

输出

输出共有 $Q$ 行。第 $j$ ($1 ≦ j ≦ Q$) 行输出处理 $j$ 个查询之前的状态下，尼万哥君和尼可尼科电视酱按照以上方法分配糖果时，尼万哥君能够获得的最大糖果数。

示例输入 1

6
3 1 4 1 5 9
1
1 3

示例输出 1

21

这是满足部分得分条件的案例。一开始，每个盘子上的糖果数从左到右分别为 $0$, $3$, $1$, $4$, $1$, $5$, $9$, $0$。

此时，对于盘子 $1$ 到 $6$，将每个盘子上的糖果移动到右边、右边、左边、右边、左边、右边相邻的盘子上，糖果数量变为 $0$, $0$, $7$, $1$, $5$, $1$, $0$, $9$。

然后移除所有没有糖果的盘子，得到 $7$, $1$, $5$, $1$, $9$，尼万哥君能够获得的最大糖果数为 $21$。这是使尼万哥君获得最多糖果的情况。

示例输入 2

5
1 2 3 4 5
1
1 1

示例输出 2

11

这是满足部分得分条件的案例。

示例输入 3

8
2 5 2 5 2 5 2 5
5
1 7
6 1
3 6
8 3
2 9

示例输出 3

27
24
24
22
26

这个示例不满足部分得分条件。