F - More Comfortable Train

問題

AAC国では、「第二鉄道」という鉄道が走っていて、その電車は非常に混みます。
その鉄道のある電車について考えます。
その電車に席は $M$ 個あり、$1$ から $M$ の番号がついて、席 $i$ と 席 $i + 1$ は隣り合っています。
$N$ 人の人が電車に乗っていて、あなたはそれぞれの人に対して「座れ」「座るな」と指示できます。
$i$ 番目の人に「座れ」と指示した場合は $A_i$ から距離が $K$ 以内（すなわち $K$ 回以下隣に移動することで到達できる）席すべてに人が座っていない場合は座ります。
「座るな」と指示した際はその場を去ります。
適切な指示を行うことで、座れる人の数を最大化してください。

制約

• $1\leq N \leq 10^5$
• $1\leq M, K\leq 10^9$
• $1\leq A_i \leq M$

入力

$N\quad M\quad K$
$A_1\quad A_2\quad\cdots\quad A_{N-1}\quad A_N$