题目描述

译自 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$ 次修改后得到的答案，第一行就代表未修改前得到的答案。

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