Elephants

You are filming an elephant show in which $N$ elephants stand in a row on a stage and dance. The elephants are numbered from $0$ to $N-1$.

The show consists of a sequence of moves. In each move, exactly one elephant walks to a different position on the stage (it may also stay where it is). Several elephants may share the same position; in that case they simply stand one behind another.

Right after each move, you want to photograph every elephant on the stage at that moment. A single camera can only photograph the elephants lying within a segment of length $L$ (both endpoints included): a camera placed at position $s$ captures every elephant in the interval $[s,\ s+L]$. When the elephants are spread out, several cameras may be needed to capture everyone at once.

After each move, determine the minimum number of cameras needed to photograph all elephants at that moment. This number may increase, decrease, or stay the same from one move to the next.

For example, if $L=10$ and the elephants are at positions $10, 15, 17, 20$, then, as shown below, a single camera captures all of them. (Triangles are elephants; the trapezoid is a camera.)

If, in the next move, the elephant at position $15$ walks to $32$, then at least two cameras are needed to capture this moment.

If, in the following move, the elephant at position $10$ walks to $7$, then three cameras are needed to photograph all elephants.

The camera segment length $L$ is an integer with $0 \le L \le 10^9$. The initial position $X[i]$ of elephant $i$ is an integer, and the positions are given sorted: $0 \le X[0] \le X[1] \le \cdots \le X[N-1] \le 10^9$. As moves are performed, the sorted order of the positions may change. Each move is given by an elephant index $i$ and a new position $y$ ($0 \le y \le 10^9$), and it changes the position of elephant $i$ to $y$.

The first line contains the number of elephants $N$, the camera segment length $L$, and the number of moves $M$, separated by spaces.

Each of the next $N$ lines contains one initial position, one per line. The $i$-th of these values is $X[i-1]$, and they are given in non-decreasing order.

Each of the following $M$ lines describes one move: two integers $i$ and $y$ separated by a space, meaning elephant $i$ moves to position $y$.

For each move, output on its own line the minimum number of cameras needed to photograph all elephants after that move, in the order the moves are given in the input.