310317: CF1814E. Chain Chips

E. Chain Chipstime limit per test3 secondsmemory limit per test512 megabytesinputstandard inputoutputstandard output

You are given an undirected graph consisting of $n$ vertices and $n-1$ edges. The $i$-th edge has weight $a_i$; it connects the vertices $i$ and $i+1$.

Initially, each vertex contains a chip. Each chip has an integer written on it; the integer written on the chip in the $i$-th vertex is $i$.

In one operation, you can choose a chip (if there are multiple chips in a single vertex, you may choose any one of them) and move it along one of the edges of the graph. The cost of this operation is equal to the weight of the edge.

The cost of the graph is the minimum cost of a sequence of such operations that meets the following condition:

• after all operations are performed, each vertex contains exactly one chip, and the integer on each chip is not equal to the index of the vertex where that chip is located.

You are given $q$ queries of the form:

• $k$ $x$ — change the weight of the $k$-th edge (the one which connects the vertices $k$ and $k+1$) to $x$.

After each query, print the cost of the graph. Note that you don't actually move any chips; when you compute the cost, the chips are on their initial positions.

Input

The first line contains one integer $n$ ($2 \le n \le 2 \cdot 10^5$).

The second line contains $n-1$ integers $a_1, a_2, \dots, a_{n-1}$ ($1 \le a_i \le 10^9$).

The third line contains one integer $q$ ($1 \le q \le 2 \cdot 10^5$).

Then $q$ lines follow. The $i$-th of them contains two integers $k$ and $x$ ($1 \le k \le n-1$; $1 \le x \le 10^9$) for the $i$-th query.

Output

For each query, print one integer — the cost of the graph after the query is performed.

ExampleInput

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

Output

126
108
120
108
112
98
98
114

题目大意：
给定一个包含n个顶点和n-1条边的无向图。第i条边的权重为a_i，连接顶点i和i+1。最初，每个顶点都有一块筹码，每块筹码上写有一个整数，第i个顶点上的筹码上的整数是i。每次操作可以选择一个筹码（如果单个顶点中有多个筹码，可以选择其中任何一个）并将其沿着图的一条边移动，此操作的成本等于边的权重。图的成本是最小操作序列的成本，满足条件：所有操作完成后，每个顶点恰好有一个筹码，且每块筹码上的整数不等于该筹码所在顶点的索引。给定q个查询，形式为：k x ——将第k条边（连接顶点k和k+1的边）的权重改为x。每次查询后，输出图的成本。注意，实际上并不移动任何筹码；在计算成本时，筹码位于它们的初始位置。

输入数据格式：
第一行包含一个整数n（2≤n≤2×10^5）。
第二行包含n-1个整数a_1, a_2, …, a_{n-1}（1≤a_i≤10^9）。
第三行包含一个整数q（1≤q≤2×10^5）。
然后是q行，每行包含两个整数k和x（1≤k≤n-1；1≤x≤10^9），代表第i个查询。

输出数据格式：
对于每个查询，输出一个整数——执行查询后图的成本。题目大意： 给定一个包含n个顶点和n-1条边的无向图。第i条边的权重为a_i，连接顶点i和i+1。最初，每个顶点都有一块筹码，每块筹码上写有一个整数，第i个顶点上的筹码上的整数是i。每次操作可以选择一个筹码（如果单个顶点中有多个筹码，可以选择其中任何一个）并将其沿着图的一条边移动，此操作的成本等于边的权重。图的成本是最小操作序列的成本，满足条件：所有操作完成后，每个顶点恰好有一个筹码，且每块筹码上的整数不等于该筹码所在顶点的索引。给定q个查询，形式为：k x ——将第k条边（连接顶点k和k+1的边）的权重改为x。每次查询后，输出图的成本。注意，实际上并不移动任何筹码；在计算成本时，筹码位于它们的初始位置。 输入数据格式： 第一行包含一个整数n（2≤n≤2×10^5）。 第二行包含n-1个整数a_1, a_2, …, a_{n-1}（1≤a_i≤10^9）。 第三行包含一个整数q（1≤q≤2×10^5）。 然后是q行，每行包含两个整数k和x（1≤k≤n-1；1≤x≤10^9），代表第i个查询。 输出数据格式： 对于每个查询，输出一个整数——执行查询后图的成本。