Alarm Clock

### 题目描述 每天晚上 Vitalya 会设置 $n$ 个闹钟以便明早醒来。每个闹钟都会正好响一分钟，并正好在那一分钟的开始响起，结束停止。给定 $a_i$ 来表示第 $i$ 个闹钟响起的时间。如果在连续的 $m$ 分钟内有至少 $k$ 个闹钟响起，Vitalya 就会醒来。注意 Vitalya 只会考虑在那一段时间中开始响起的闹钟，即不考虑在之前已经响起而未停止响的闹钟。 Vitalya 十分疲劳，他想睡整整一天而不起床。您的任务是计算出需要关掉的闹钟总数的最小值。开始时所有闹钟都是打开状态。 ### 输入格式 第一行包含三个整数 $n , m , k (1\le k\le n\le2\times10^5, 1\le m\le10^6)$，分别表示闹钟总个数个数和 Vitalya 醒来的条件中连续时间段的长度和闹钟响起的个数。 第二行包含 $n$ 个整数 $a_1,a_2,\cdots,a_n(1\le a_i\le10^6)$，分别表示第 $i$ 个闹钟响起的时间（单位：分钟）。 注意 $a_i$ 为乱序。Vitalya 的国度一天有 $10^6$ 分钟。 ### 输出格式 一行一个整数，表示最少需要关闭的闹钟个数。

Every evening Vitalya sets $ n $ alarm clocks to wake up tomorrow. Every alarm clock rings during exactly one minute and is characterized by one integer $ a_{i} $ — number of minute after midnight in which it rings. Every alarm clock begins ringing at the beginning of the minute and rings during whole minute. Vitalya will definitely wake up if during some $ m $ consecutive minutes at least $ k $ alarm clocks will begin ringing. Pay attention that Vitalya considers only alarm clocks which begin ringing during given period of time. He doesn't consider alarm clocks which started ringing before given period of time and continues ringing during given period of time. Vitalya is so tired that he wants to sleep all day long and not to wake up. Find out minimal number of alarm clocks Vitalya should turn off to sleep all next day. Now all alarm clocks are turned on.

First line contains three integers $ n $ , $ m $ and $ k $ ( $ 1<=k<=n<=2·10^{5} $ , $ 1<=m<=10^{6} $ ) — number of alarm clocks, and conditions of Vitalya's waking up. Second line contains sequence of distinct integers $ a_{1},a_{2},...,a_{n} $ ( $ 1<=a_{i}<=10^{6} $ ) in which $ a_{i} $ equals minute on which $ i $ -th alarm clock will ring. Numbers are given in arbitrary order. Vitalya lives in a Berland in which day lasts for $ 10^{6} $ minutes.

Output minimal number of alarm clocks that Vitalya should turn off to sleep all next day long.

3 3 2
3 5 1

1

5 10 3
12 8 18 25 1

0

7 7 2
7 3 4 1 6 5 2

6

2 2 2
1 3

0

In first example Vitalya should turn off first alarm clock which rings at minute $ 3 $ . In second example Vitalya shouldn't turn off any alarm clock because there are no interval of $ 10 $ consequence minutes in which $ 3 $ alarm clocks will ring. In third example Vitalya should turn off any $ 6 $ alarm clocks.