问题陈述
高桥将在酒店住宿 N 天。
酒店有清洁服务,他打算使用 K 次,
当天 D_1,日 D_2, \ldots和日期 D_K,在他的 N天访问。
然而事实证明该服务最多可用
任何连续的 M 次 L 天。
更正式地说,对于所有整数 i 与 1\leq i\leq N-L+1,
该服务最多可用
一天中的 M 次 i 全天 (i+L-1).
他决定取消一些在几天内使用该服务的计划 D_1, D_2, \ldots,和 D_K,满足这些条件。 (他可能根本不需要取消他的计划。) 其中至少有多少天 K 需要多少天取消使用计划才能满足条件?
约束
- 1\leq L \leq N \leq 10^{18}
- 1\leq M \leq K \leq 2\times 10^5
- 1\leq D_1<D_2<\cdots<D_K\leq N
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
N K L M D_1 D_2 \ldots D_K
输出
打印至少需要取消多少次使用清洁服务的计划才能满足条件。
示例输入 1
10 6 5 2 1 2 3 6 8 10
示例输出 1
2
连续五天内最多提供两次清洁服务。
取消当天的使用计划即可满足条件 2 和 10,并在当天使用它 1,3,6,和 8.
无论选择六个中的哪一个,仅取消一次都不会满足条件,因此打印 2.
示例输入 2
10 3 3 1 1 5 10
示例输出 2
0
他根本不需要取消计划。
示例输入 3
1000000000000000000 2 1000000000000000000 1 1 1000000000000000000
示例输出 3
1