链上芯片

• 时间限制：3 秒
• 内存限制：512 MiB

题目描述

有一张由 $n$ 个顶点组成的无向链。第 $i$ 条边连接顶点 $i$ 和 $i+1$，边权为 $a_i$。

初始时，每个顶点上恰有一个芯片；顶点 $i$ 上芯片的编号为 $i$。一次操作可以选择任意一个芯片，把它沿链上的一条边移动，代价等于这条边的边权。

你需要让所有芯片移动结束后仍满足每个顶点恰有一个芯片，并且每个芯片的编号都不等于它所在顶点的编号。定义当前链的总代价为达成该目标所需的最小操作代价。

接下来有 $q$ 次修改。每次把一条边的边权改为给定值，并询问修改后的总代价。各次修改会保留，但计算答案时芯片始终视为从初始位置出发，你只需输出最小代价，不必实际构造移动方案。

输入格式

第一行一个整数 $n$。

第二行 $n-1$ 个整数 $a_1,a_2,\ldots,a_{n-1}$。

第三行一个整数 $q$。

接下来 $q$ 行，每行两个整数 $k,x$，表示把第 $k$ 条边的边权修改为 $x$。

输出格式

对每次修改输出一行一个整数，表示修改后的最小总代价。

样例输入 1

10
12 6 12 15 20 8 17 12 15
8
4 10
7 3
6 14
9 9
2 10
3 5
4 11
7 11

样例输出 1

126
108
120
108
112
98
98
114

数据范围

保证 $2\le n,q\le2\times10^5$，$1\le a_i,x\le10^9$。

所有测试点相互独立计分。