自动停止的淋浴AI (CI翻译)
Problem Statement
题目描述
AI (CI翻译)Takahashi is using a shower at a public bath. This shower has a button. If the button is pressed at time $t$, hot water comes out for $K$ seconds, from time $t$ to time $t+K$. Even if the button is pressed again while hot water is coming out, hot water comes out for $K$ seconds from the time the button was last pressed.
高桥正在公共澡堂淋浴。淋浴装置上有一个按钮。若在时刻 $t$ 按下按钮，热水会从时刻 $t$ 持续流出 $K$ 秒，即一直流到时刻 $t+K$。即使热水正在流出时再次按下按钮，热水也会从最后一次按下按钮的时刻起持续流出 $K$ 秒。AI (CI翻译)
There are $N$ Aokis, each of whom presses the button once. The $i$-th Aoki presses the button at time $A_i$.
有 $N$ 位青木，他们每人都会按一次按钮。第 $i$ 位青木在时刻 $A_i$ 按下按钮。AI (CI翻译)
Find the minimum number of times Takahashi needs to press the button so that hot water is always coming out from time $0$ to time $T$. Here, hot water is considered to be coming out both at the moment the button is pressed and at the moment exactly $K$ seconds after the last press.
求高桥至少需要按多少次按钮，才能保证热水在从时刻 $0$ 到时刻 $T$ 的整个时间段内一直流出。这里认为在按下按钮的瞬间，以及距离最后一次按下按钮恰好 $K$ 秒的瞬间，热水也在流出。AI (CI翻译)
Constraints
约束条件
AI (CI翻译)$1 \leq N \leq 2 \times 10^5$$1 \leq K \leq 10^9$$1 \leq T \leq 10^9$$0 \leq A_i \leq 10^9$- All input values are integers.
$1 \leq N \leq 2 \times 10^5$$1 \leq K \leq 10^9$$1 \leq T \leq 10^9$$0 \leq A_i \leq 10^9$- 所有输入值均为整数。
Input
输入格式
AI (CI翻译)The input is given from Standard Input in the following format:
输入从标准输入按以下格式给出：AI (CI翻译)
N K T
A_1 A_2 \ldots A_NN K T
A_1 A_2 \ldots A_NOutput
输出格式
AI (CI翻译)Print the answer in a single line.
在一行中输出答案。AI (CI翻译)
样例
3 4 20
6 7 12
4
9 37 480
12 123 132 213 231 312 321 500 1000
11
题面与样例版权归 AtCoder 及出题人所有；中文翻译由 AI 生成（gpt-6.1-sol），如有出入请以原文为准。