UOJ Logo LFYZ Online Judge

LFYZOJ

#52. 【2018年2月期末欢乐赛】闹钟托起秋穰子

统计

问题描述

这天早晨,秋穰子又躺在床上。

“我不想起床(>_<)”

可惜的是,秋静叶早已把 $n$ 个闹钟放在了穰子的床头。第 $i$ 个闹钟会在第 $a_i$ 分钟初响起,刚好持续 1 分钟。

幻想乡的一个早上挺长。反正比人类的长多了。在幻想乡内可没有什么常识呦。

同为不人气姐妹的九十九姐妹中的九十九八桥看见这个充满闹钟的修罗场于心不忍,她知道,如果在 $m$ 分钟内有大于等于 $k$ 个闹钟作响,可怜的穰子就会醒来。八桥决定让九十九弁弁去掉一些闹钟,让穰子美美地睡上一早上而不被闹钟惊醒。

请你告诉弁弁,她最少要去掉多少闹钟,才会让穰子不被惊醒。

输入格式

第一行三个整数 $n,m,k$。

第二行 $n$ 个整数,第 $i$ 个代表着 $a_i$。

输出格式

一个整数,是弁弁最少去掉闹钟数。

样例一

input

3 3 2
3 5 1

output

1

样例二

input

5 10 3
12 8 18 25 1

output

0

样例三

input

7 7 2
7 3 4 1 6 5 2

output

6

样例四

input

2 2 2
1 3

output

0

数据范围与约定

对于 $100\%$ 的数据,$1 \leq k \leq n \leq 2 \times 10^5$,$1 \leq m \leq 10^6$,$1 \leq a_i \leq 10^6$,保证 $a_i$ 互不相同。

时间限制: $1\mathrm{s}$

内存限制: $256\mathrm{MB}$

来源

cf 898d