题目描述
译自 Canadian Computing Olympiad 2018 Day 2 B 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$ 行是未修改前的答案）。

样例
输入

4 3 1
6 1 2 4
1 3

输出

8
6

解释：

• 未修改时，选定区间 $[1,3]$，得到的和为 $6+2=8$。
• 第一次修改后，选定区间 $[2,4]$，得到的和为 $2+4=6$。

数据范围与提示
对于全部数据：

• $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$。