코끼리

무대 위에서 $N$마리의 코끼리가 한 줄로 서서 춤을 추는 코끼리 쇼를 촬영하려고 한다. 코끼리들은 $0$번부터 $N-1$번까지 번호가 매겨져 있다.

쇼는 여러 번의 동작으로 이루어진다. 각 동작에서는 정확히 한 마리의 코끼리만 무대 위의 다른 위치로 이동한다(제자리에 그대로 있을 수도 있다). 여러 마리의 코끼리가 같은 위치에 겹쳐 서 있을 수도 있으며, 이때는 단순히 서로의 뒤에 서 있는 것으로 본다.

각 동작이 끝난 직후, 그 순간 무대 위의 모든 코끼리를 사진에 담으려고 한다. 하나의 카메라는 길이가 $L$인 구간(양 끝 포함) 안에 있는 코끼리들만 한 번에 찍을 수 있다. 즉 어떤 카메라가 위치 $s$에서 시작하면 구간 $[s,\ s+L]$ 안의 모든 코끼리를 찍는다. 코끼리들이 넓게 흩어져 있으면 한 순간을 모두 담기 위해 카메라가 여러 대 필요할 수 있다.

각 동작이 끝난 뒤, 그 순간의 모든 코끼리를 찍는 데 필요한 카메라의 최소 개수를 구하라. 이 값은 동작마다 늘어날 수도, 줄어들 수도, 그대로일 수도 있다.

예를 들어 $L=10$이고 코끼리들이 위치 $10, 15, 17, 20$에 있다면, 아래 그림처럼 카메라 한 대로 모든 코끼리를 담을 수 있다. (삼각형은 코끼리를, 사다리꼴은 카메라를 나타낸다.)

이어지는 동작에서 위치 $15$에 있던 코끼리가 $32$로 이동하면, 이 순간을 담기 위해서는 카메라가 적어도 두 대 필요하다.

그다음 동작에서 위치 $10$에 있던 코끼리가 $7$로 이동하면, 모든 코끼리를 담는 데 카메라 세 대가 필요하다.

카메라 구간의 길이 $L$은 정수이며 $0 \le L \le 10^9$이다. 처음에 주어지는 코끼리 $i$의 위치 $X[i]$는 정수이고 $0 \le X[0] \le X[1] \le \cdots \le X[N-1] \le 10^9$로 오름차순 정렬되어 있다. 동작이 진행되면 위치들의 정렬 순서는 바뀔 수 있다. 각 동작은 코끼리 번호 $i$와 새 위치 $y$($0 \le y \le 10^9$)로 주어지며, 코끼리 $i$의 위치를 $y$로 바꾼다.

첫째 줄에 코끼리의 수 $N$, 카메라 구간의 길이 $L$, 동작의 수 $M$이 공백으로 구분되어 주어진다.

이어지는 $N$개의 줄에는 코끼리들의 초기 위치가 한 줄에 하나씩 주어진다. $i$번째 값은 $X[i-1]$이며, 오름차순으로 정렬되어 있다.

그다음 $M$개의 줄에는 각 동작이 한 줄에 하나씩 주어진다. 각 줄에는 두 정수 $i$와 $y$가 공백으로 구분되어 있으며, 코끼리 $i$가 위치 $y$로 이동함을 뜻한다.

각 동작마다, 그 동작이 끝난 뒤 모든 코끼리를 찍는 데 필요한 카메라의 최소 개수를 한 줄에 하나씩, 입력에 주어진 동작 순서대로 출력한다.