Alarm Clock

题意翻译

题目描述 每天晚上Vitalya会设置 n 个闹钟以便明早醒来。每个闹钟都会正好响一分钟，并正好在那一分钟的开始响起，结束停止。给定ai来表示第i个闹钟响起的时间。如果在连续的 m 分钟内有至少 k 个闹钟响起，Vitalya就会醒来。注意Vitalya只会考虑在那一段时间中开始响起的闹钟，即不考虑在之前已经响起而未停止响的闹钟。 Vitalya十分疲劳，他想睡整整一天而不起床。您的任务是计算出需要关掉的闹钟总数的最小值。开始时所有闹钟都是打开状态。 输入输出格式 输入格式 第一行包含三个整数 n , m , k (1<=k<=n<=2e5, 1<=m<=1e6)，分别表示闹钟总个数个数和Vitalya醒来的条件中连续时间段的长度和闹钟响起的个数。 第二行包含n个整数a1,a2,...an(1<=ai<=1e6)，分别表示第i个闹钟响起的时间（单位：分钟）。注意ai为乱序。Vitalya的国度一天有1e6分钟。 输出格式 输出最少需要关闭的闹钟个数。 感谢@LPA20020220 提供的翻译

题目描述

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.

输入输出样例

输入样例 #1

3 3 2
3 5 1

输出样例 #1

1

输入样例 #2

5 10 3
12 8 18 25 1

输出样例 #2

0

输入样例 #3

7 7 2
7 3 4 1 6 5 2

输出样例 #3

6

输入样例 #4

2 2 2
1 3

输出样例 #4

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.