P6717 [CCO 2018] Boring Lectures

有一个长为 $N$ 的数列，第 $i$ 个数为 $a_i$。 有 $Q$ 次修改，第 $j$ 次会将第 $i_j$ 个数改成 $x_j$。 您需要求出在最初和每次修改之后连续的的 $K$ 个元素中，最大值与次大值的和最大是多少。

第一行三个整数 $N,K,Q$ 见题目描述。 第二行 $N$ 个整数 $a_i$ 为这个序列。 接下来 $Q$ 行每行两个整数 $i_j,x_j$ 代表一次更改。

$Q+1$ 行第 $j$ 行代表第 $j-1$ 次修改后得到的答案，第一行就代表未修改前得到的答案。

#### 样例说明 对于样例 $1$ - 还未修改时，我们选定 $[1,3]$，得到的和为 $6+2=8$ - 进行第一次修改时，我们选定 $[2,4]$，得到的和为 $2+4=6$ #### 数据规模与约定 对于 $100\%$ 的数据，$2 \le N \le 10^6$，$2 \le K \le N$，$0 \le Q \le 10^5$，$0 \le a_i \le 10^9$，$1 \le i_j \le N$，$0 \le x_j \le 10^9$。 对于 $20\%$ 的数据，$Q=0$。 对于另外 $40\%$ 的数据，$N \le 10^4$。 #### 说明 翻译自 [Canadian Computing Olympiad 2018](https://cemc.math.uwaterloo.ca/contests/computing/2018/) Day 2 [B Boring Lectures](https://cemc.math.uwaterloo.ca/contests/computing/2018/stage%202/day2.pdf)。