지루한 강의

시간 제한8초메모리 제한512 MB

요약

배열의 값이 바뀔 때마다 길이 K인 구간 하나를 고르고, 그 안에서 두 원소의 합을 최대로 만드는 값을 구합니다.

난이도: 어려움10점 중 8점
유형: 세그먼트 트리, 슬라이딩 윈도우, 배열
정답자: 아직 제출이 없습니다

문제

앞으로 열리는 $N$ 개의 강의가 있고, 그중 일부에 출석할지 선택할 수 있다. 강의는 시간 순서대로 1번부터 $N$ 번까지 번호가 매겨져 있다. 현재 일정에서 $i$ 번째 강의의 품질은 $a_i$ 이다. 대부분의 강의가 지루하므로, 연속된 $K$ 개의 강의 묶음 하나만 듣고 나머지는 건너뛰어 잠을 자거나 프로그래밍 대회를 준비한다. 메모하는 것을 싫어해서, 들은 강의 중 2개의 내용만 기억할 수 있다. 연속된 $K$ 개 강의 묶음과 기억할 2개 강의를 골라 기억한 2개 강의 품질의 합이 최대가 되게 하라.

일정에는 $Q$ 번의 변경이 있다. $j$ 번째 변경은 두 값 $i_j$ , $x_j$ 로 주어지며, $i_j$ 번째 강의의 품질이 $x_j$ 로 바뀐다는 뜻이다. 일정 $Q+1$ 개 각각에 대해 강의 품질 합의 최댓값을 구하라.

입력

첫 줄에 세 정수 $N$ , $K$ , $Q$ 가 주어진다 ( $2 \le N \le 10^6$ , $2 \le K \le N$ , $0 \le Q \le 10^5$ ). 둘째 줄에는 $N$ 개의 정수 $a_1, \ldots, a_N$ 이 주어진다 ( $0 \le a_i \le 10^9$ ). 이어지는 $Q$ 개의 줄에는 각각 두 정수 $i_j$ , $x_j$ 가 주어진다 ( $1 \le i_j \le N$ , $0 \le x_j \le 10^9$ ).

출력

$Q+1$ 개의 줄을 출력한다. $j$ 번째 줄에는 처음 $j-1$ 번의 변경을 적용한 뒤의 일정에 대한 답을 출력한다.

예제1

예제 1
입력
```
4 3 1
6 1 2 4
1 3
```
예상 출력
```
8
6
```