You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目背景

一年一度的烟花大会开始了！

题目描述

共有 $N$ 个烟花，从左到右编号为 $1 \sim N$。每个烟花都有自己的燃放时间，第 $i$ 个烟花会在第 $t_i$ 个时刻点被点燃。另外相邻两个烟花存在着特殊的单向引线，第 $i$ 个烟花点燃后，如果第 $i+1$ 个烟花此时未被点燃，那么它会在第 $t_i+1$ 个时间点点燃而不是 $t_{i + 1}$。

现在你有机会断掉 $D$ 条单向引线，在时间 $T$ 及以前最少会有多少烟花被点燃？

输入格式

第一行三个整数 $N,D,T$ 代表烟花个数，可以断掉引线的个数和询问时间。

第二行 $N$ 个整数 $t_i$ 代表第 $i$ 个烟花被点燃的时间。

输出格式

一行一个整数代表答案。

5 1 42
13 37 47 11 42

4

5 2 5
1 9 4 6 7

2

20 4 14
8 11 2 9 8 16 18 9 13 9 1 2 3 16 12 15 6 19 15 15

13

20 4 8
1 9 17 18 15 8 19 13 15 14 17 9 3 7 20 11 2 16 14 11

5

提示

本题采用捆绑测试。

• 对于 $15\%$ 的数据满足 $N \le 500$。
• 对于 $35\%$ 的数据满足 $N \le 4000$。
• 对于 $60\%$ 的数据满足 $N \le 7.5 \times 10^4$
• 对于额外 $10\%$ 的数据满足：$N \le 5 \times 10^5$，$D=1$。
• 对于额外 $10\%$ 的数据满足：$N \le 7.5 \times 10^4$，$D \le 15$。
• 对于 $100\%$ 的数据，$1 \le D<N \le 2 \times 10^6$，$1 \le T,t_i \le 10^9$。