Description

There is a sequence of length $N$, where the $i$-th number is $a_i$.

There are $Q$ modifications. In the $j$-th modification, the number at position $i_j$ is changed to $x_j$.

You need to find, for the initial sequence and after each modification, the maximum possible value of the sum of the largest and second largest elements among all consecutive subarrays of length $K$.

Input Format

The first line contains three integers $N, K, Q$, as described above.
The second line contains $N$ integers $a_i$, the sequence.
The next $Q$ lines each contain two integers $i_j, x_j$, representing one modification.

Output Format

Output $Q+1$ lines. The $j$-th line represents the answer after the $(j-1)$-th modification. The first line represents the answer before any modifications.

4 3 1
6 1 2 4
1 3

8
6

Hint

Sample Explanation

For Sample $1$.

• Before any modification, we choose $[1,3]$, and the sum is $6+2=8$.
• After the first modification, we choose $[2,4]$, and the sum is $2+4=6$.

Constraints

For $100\%$ of the testdata, $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$.
For $20\%$ of the testdata, $Q=0$.
For another $40\%$ of the testdata, $N \le 10^4$.

Notes

Translated from Canadian Computing Olympiad 2018 Day 2 B Boring Lectures。

Translated by ChatGPT 5