自停淋浴

题目描述

高桥正在公共澡堂里洗澡。这个淋浴有一个按钮：如果在时刻 $t$ 按下按钮，热水会从时刻 $t$ 起持续流出 $K$ 秒，也就是从时刻 $t$ 到时刻 $t+K$。即使热水正在流出时再次按下按钮，热水也只是从最后一次按下按钮的时刻起再流出 $K$ 秒。

澡堂里有 $N$ 个青木，每人都会按下一次按钮。第 $i$ 个青木在时刻 $A_i$ 按下按钮。

请计算：为了让热水从时刻 $0$ 到时刻 $T$ 一直不断地流出，高桥最少需要按多少次按钮。

按下按钮的那一刻，以及最后一次按下按钮之后恰好 $K$ 秒的那一刻，都算作「热水正在流出」。

输入格式

第一行三个整数 $N, K, T$，相邻两个整数之间用一个空格隔开。

第二行 $N$ 个整数 $A_1, A_2, \dots, A_N$，相邻两个整数之间用一个空格隔开。

输出格式

输出一行一个整数，表示高桥最少需要按按钮的次数。

3 4 20
6 7 12

4

样例 1 解释

如果高桥在时刻 $0, 2, 10, 16$ 按下按钮，那么热水会一直流到时刻 $20$：

• 高桥在时刻 $0$、$2$ 按下，热水分别覆盖 $[0, 4]$ 与 $[2, 6]$，合起来是 $[0, 6]$；
• 青木在时刻 $6$ 按下，热水覆盖 $[6, 10]$（青木在时刻 $7$ 按下的那次覆盖 $[7, 11]$，也落在其中）；
• 高桥在时刻 $10$ 按下，热水覆盖 $[10, 14]$；青木在时刻 $12$ 按下，热水覆盖 $[12, 16]$；
• 高桥在时刻 $16$ 按下，热水覆盖 $[16, 20]$。

按 $3$ 次或更少无法让热水一直流到时刻 $20$，所以答案是 $4$。

9 37 480
12 123 132 213 231 312 321 500 1000

11

数据范围

对于所有测试数据，保证：

• $1 \le N \le 2 \times 10^5$；
• $1 \le K \le 10^9$；
• $1 \le T \le 10^9$；
• $0 \le A_i \le 10^9$；
• 所有输入值都是整数。

子任务

本题共 20 个测试点，按测试点计分：

每个测试点单独评分，全部测试点的得分之和即为本题得分。