给定一个由 $$$n$$$ 个顶点和 $$$n-1$$$ 边组成的无向图。第 $$$i$$$ 条边的权重为 $$$a_i$$$;它连接顶点 $$$i$$$ 和 $$$i+1$$$。
最初,每个顶点都包含一个芯片。每个芯片上都写有一个整数;写在芯片上第 $$$i$$$ 个顶点的整数是 $$$i$$$。
在一次操作中,您可以选择一个芯片(如果单个顶点中有多个芯片,您可以选择其中任何一个)并将其沿图的一条边移动。该操作的成本等于边的权重。
图的成本是满足以下条件的一系列此类操作的最小成本:
- 执行完所有操作后,每个顶点恰好包含一个筹码,并且每个筹码上的整数不等于该筹码所在顶点的索引。
您将收到以下形式的 $$$q$$$ 查询:
- $$$k$$$ $$$x$$$ — 将第 $$$k$$$ 条边(连接顶点 $$$k$$$ 和 $$$k+1$$$ 的边)的权重更改为 $$$x$$$。
每次查询后,打印图表的成本。请注意,您实际上并没有移动任何筹码;而是移动了任何筹码。当你计算成本时,筹码处于其初始位置。
输入
第一行包含一个整数 $$$n$$$ ($$$2 \le n \le 2 \cdot 10^5$$$)。
第二行包含 $$$n-1$$$ 整数 $$$a_1, a_2, \dots, a_{n-1}$$$ ($$$1 \le a_i \le 10^9$$$)。
第三行包含一个整数$$$q$$$ ($$$1 \le q \le 2 \cdot 10^5$$$)。
然后是 $$$q$$$ 行。其中第 $$$i$$$ 包含第 $$$i$$$ 查询的两个整数 $$$k$$$ 和 $$$x$$$ ($$$1 \le k \le n-1$$$; $$$1 \le x \le 10^9$$$)。
输出
对于每个查询,打印一个整数 - 执行查询后图表的成本。
示例
输入 #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