English · Original
Chinese · Translation
Formal · Original
ZS the Coder is coding on a crazy computer. If you don't type in a word for a _c_ consecutive seconds, everything you typed disappear!
More formally, if you typed a word at second _a_ and then the next word at second _b_, then if _b_ - _a_ ≤ _c_, just the new word is appended to other words on the screen. If _b_ - _a_ > _c_, then everything on the screen disappears and after that the word you have typed appears on the screen.
For example, if _c_ = 5 and you typed words at seconds 1, 3, 8, 14, 19, 20 then at the second 8 there will be 3 words on the screen. After that, everything disappears at the second 13 because nothing was typed. At the seconds 14 and 19 another two words are typed, and finally, at the second 20, one more word is typed, and a total of 3 words remain on the screen.
You're given the times when ZS the Coder typed the words. Determine how many words remain on the screen after he finished typing everything.
## Input
The first line contains two integers _n_ and _c_ (1 ≤ _n_ ≤ 100 000, 1 ≤ _c_ ≤ 109) — the number of words ZS the Coder typed and the crazy computer delay respectively.
The next line contains _n_ integers _t_1, _t_2, ..., _t__n_ (1 ≤ _t_1 < _t_2 < ... < _t__n_ ≤ 109), where _t__i_ denotes the second when ZS the Coder typed the _i_\-th word.
## Output
Print a single positive integer, the number of words that remain on the screen after all _n_ words was typed, in other words, at the second _t__n_.
[samples]
## Note
The first sample is already explained in the problem statement.
For the second sample, after typing the first word at the second 1, it disappears because the next word is typed at the second 3 and 3 - 1 > 1. Similarly, only 1 word will remain at the second 9. Then, a word is typed at the second 10, so there will be two words on the screen, as the old word won't disappear because 10 - 9 ≤ 1.
ZS the Coder 正在一台疯狂的电脑上打字。如果你在连续 #cf_span[c] 秒内不输入任何单词，所有已输入的内容都会消失！
更正式地，如果你在第 #cf_span[a] 秒输入了一个单词，然后在第 #cf_span[b] 秒输入了下一个单词，那么如果 #cf_span[b - a ≤ c]，新单词将被追加到屏幕上的其他单词之后；如果 #cf_span[b - a > c]，则屏幕上的所有内容都会清空，之后仅显示你刚刚输入的单词。
例如，如果 #cf_span[c = 5]，你在秒数 #cf_span[1, 3, 8, 14, 19, 20] 输入单词，那么在第 #cf_span[8] 秒时，屏幕上会有 #cf_span[3] 个单词。之后，在第 #cf_span[13] 秒时，由于没有输入任何内容，所有内容都会消失。在第 #cf_span[14] 和 #cf_span[19] 秒，又分别输入了两个单词，最后在第 #cf_span[20] 秒输入了一个单词，最终屏幕上保留了 #cf_span[3] 个单词。
给你 ZS the Coder 输入单词的时间点，请确定他在完成所有输入后，屏幕上剩余多少个单词。
第一行包含两个整数 #cf_span[n] 和 #cf_span[c] (#cf_span[1 ≤ n ≤ 100 000, 1 ≤ c ≤ 109]) —— 分别表示 ZS the Coder 输入的单词数量和疯狂电脑的延迟时间。
第二行包含 #cf_span[n] 个整数 #cf_span[t1, t2, ..., tn] (#cf_span[1 ≤ t1 < t2 < ... < tn ≤ 109])，其中 #cf_span[ti] 表示 ZS the Coder 在第 #cf_span[i] 个单词输入时的秒数。
请输出一个正整数，表示在输入完所有 #cf_span[n] 个单词后（即在第 #cf_span[tn] 秒时），屏幕上剩余的单词数量。
第一个样例已在题目描述中解释。
对于第二个样例，在第 #cf_span[1] 秒输入第一个单词后，它会消失，因为下一个单词在第 #cf_span[3] 秒输入，且 #cf_span[3 - 1 > 1]。类似地，在第 #cf_span[9] 秒时，屏幕上仅剩 #cf_span[1] 个单词。然后在第 #cf_span[10] 秒输入一个单词，此时屏幕上会有两个单词，因为旧单词不会消失（#cf_span[10 - 9 ≤ 1]）。
## Input
第一行包含两个整数 #cf_span[n] 和 #cf_span[c] (#cf_span[1 ≤ n ≤ 100 000, 1 ≤ c ≤ 109]) —— 分别表示 ZS the Coder 输入的单词数量和疯狂电脑的延迟时间。第二行包含 #cf_span[n] 个整数 #cf_span[t1, t2, ..., tn] (#cf_span[1 ≤ t1 < t2 < ... < tn ≤ 109])，其中 #cf_span[ti] 表示 ZS the Coder 在第 #cf_span[i] 个单词输入时的秒数。
## Output
请输出一个正整数，表示在输入完所有 #cf_span[n] 个单词后（即在第 #cf_span[tn] 秒时），屏幕上剩余的单词数量。
[samples]
## Note
第一个样例已在题目描述中解释。对于第二个样例，在第 #cf_span[1] 秒输入第一个单词后，它会消失，因为下一个单词在第 #cf_span[3] 秒输入，且 #cf_span[3 - 1 > 1]。类似地，在第 #cf_span[9] 秒时，屏幕上仅剩 #cf_span[1] 个单词。然后在第 #cf_span[10] 秒输入一个单词，此时屏幕上会有两个单词，因为旧单词不会消失（#cf_span[10 - 9 ≤ 1]）。
Let $ n $ and $ c $ be given integers, with $ 1 \leq n \leq 100{,}000 $ and $ 1 \leq c \leq 10^9 $.
Let $ t_1, t_2, \dots, t_n $ be a strictly increasing sequence of integers such that $ 1 \leq t_1 < t_2 < \dots < t_n \leq 10^9 $, representing the seconds at which words are typed.
Define a sequence of screen states:
At time $ t_i $, if $ i = 1 $, the screen contains 1 word.
For $ i > 1 $, if $ t_i - t_{i-1} \leq c $, then the screen retains all previous words and appends the new one.
If $ t_i - t_{i-1} > c $, then the screen is cleared, and only the new word remains.
Let $ k $ be the number of words remaining on the screen at time $ t_n $.
Then $ k $ is the length of the longest suffix of the sequence $ t_1, t_2, \dots, t_n $ such that for every consecutive pair $ t_j, t_{j+1} $ in the suffix (with $ j \geq i $), $ t_{j+1} - t_j \leq c $.
Equivalently, define $ k $ as the largest integer such that for all $ i $ from $ n - k + 1 $ to $ n - 1 $, $ t_{i+1} - t_i \leq c $.
Thus,
$$
k = \min\left(n, \max\left\{ j \in \{1, 2, \dots, n\} : \forall i \in \{n - j + 1, \dots, n - 1\},\ t_{i+1} - t_i \leq c \right\} \right)
$$
Alternatively, compute $ k $ iteratively:
Start from the last word and traverse backwards until the first gap $ t_{i+1} - t_i > c $ is found.
Then $ k $ is the number of consecutive words from the end satisfying $ t_{i+1} - t_i \leq c $, including the last word.
Formally:
Let $ k = 1 $.
For $ i = n-1 $ down to $ 1 $:
If $ t_{i+1} - t_i \leq c $, then $ k \leftarrow k + 1 $,
Else, break.
Output $ k $.
API Response (JSON)
{
"problem": {
"name": "A. Crazy Computer",
"description": {
"content": "ZS the Coder is coding on a crazy computer. If you don't type in a word for a _c_ consecutive seconds, everything you typed disappear! More formally, if you typed a word at second _a_ and then the ne",
"description_type": "Markdown"
},
"platform": "Codeforces",
"limit": {
"time_limit": 2000,
"memory_limit": 262144
},
"difficulty": "None",
"is_remote": true,
"is_sync": true,
"sync_url": null,
"sign": "CF716A"
},
"statements": [
{
"statement_type": "Markdown",
"content": "ZS the Coder is coding on a crazy computer. If you don't type in a word for a _c_ consecutive seconds, everything you typed disappear!\n\nMore formally, if you typed a word at second _a_ and then the ne...",
"is_translate": false,
"language": "English"
},
{
"statement_type": "Markdown",
"content": "ZS the Coder 正在一台疯狂的电脑上打字。如果你在连续 #cf_span[c] 秒内不输入任何单词，所有已输入的内容都会消失！\n\n更正式地，如果你在第 #cf_span[a] 秒输入了一个单词，然后在第 #cf_span[b] 秒输入了下一个单词，那么如果 #cf_span[b - a ≤ c]，新单词将被追加到屏幕上的其他单词之后；如果 #cf_span[b - a > c]，则屏幕上...",
"is_translate": true,
"language": "Chinese"
},
{
"statement_type": "Markdown",
"content": "Let $ n $ and $ c $ be given integers, with $ 1 \\leq n \\leq 100{,}000 $ and $ 1 \\leq c \\leq 10^9 $. \nLet $ t_1, t_2, \\dots, t_n $ be a strictly increasing sequence of integers such that $ 1 \\leq t_1 ...",
"is_translate": false,
"language": "Formal"
}
]
}