← 返回题目列表

Codeforces · 898/D

D. 闹钟

中文机器翻译题面 查看原题

每天晚上,Vitalya 都会设置 n 个闹钟,以便明天醒来。每个闹钟只在一分钟内响起,并由一个整数 ai 来表征 - 午夜后闹钟响起的分钟数。每个闹钟在每分钟开始时开始响铃,并在整个分钟内响铃。

如果在连续 m 分钟内至少有 k 个闹钟开始响起,Vitalya 肯定会醒来。请注意,Vitalya 只考虑在给定时间段内开始响起的闹钟。他不考虑在给定时间段之前开始响铃并在给定时间段内继续响铃的闹钟。

Vitalya 太累了,他想睡一整天而不醒来。找出维塔利亚第二天睡觉时应该关闭的最少闹钟数量。现在所有闹钟都已打开。

输入

第一行包含三个整数 n、m 和 k (1 ≤ k ≤ n ≤ 2·105, 1 ≤ m ≤ 106) — 闹钟数量和 Vitalya 醒来的条件。

第二行包含不同整数 a1, a2, ..., an (1 ≤ ai ≤ 106) 的序列,其中 ai 等于第 i 个闹钟响起的分钟。数字以任意顺序给出。维塔利亚住在 Berland,一天有 106 分钟。

输出

输出维塔利亚第二天应该关闭以睡觉的最少闹钟数量。

示例

输入 #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

注意

在第一个示例中,Vitalya 应关闭第 3 分钟响起的第一个闹钟。

在第二个示例中,Vitalya 不应关闭任何闹钟,因为在 10 分钟内没有 3 个闹钟会响的间隔。

在第三个示例中,Vitalya 应关闭任意 6 个闹钟。