| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 1024 MB | 30 | 17 | 14 | 60.870% |
A subsequence of a given sequence of integers is a subset of the values in the sequence in the same order. A k-gap subsequence of a sequence of integers is a subsequence such that consecutive elements in the subsequence differ by at least k. For example, the sequence
3, 12, 8, 4, 2, 5, 1, 9, 8, 6, 5, 1, 7
has a 4-gap subsequence of 3, 12, 8, 4, 9, 5, 1 and 7 (highlighted in bold above) since
|3 - 12|, |12 - 8|, |8 - 4|, |4 - 9|, |9 - 5|, |5 - 1| and |1 - 7| are all 4 or greater.
Given a sequence and a value of k, determine the length of the longest k-gap subsequence.
The first input line contains two space separated integers: n (1 ≤ n ≤ 300,000), indicating the length of the sequence, and k (1 ≤ k ≤ 109), indicating the value of k for the input case.
The following input line contains n space separated integers. The ith of these integers is ai (1 ≤ ai ≤ 109), the ith value of the input sequence.
Print the length of the longest k-gap subsequence of the input sequence.
10 2 1 2 3 2 1 3 1 3 5 6
7
5 12 3 7 14 20 32
3
13 4 3 12 8 4 2 5 1 9 8 6 5 1 7
8