3760 - 音符
Description

大 G 在拥有强大的算法知识储备的同时,还会创作悦耳动听的乐曲,因此深得系里学妹的追捧。

大 G 手上有 n 个音符,每个音符都有一个音高值。如果一个乐曲中有两个音符的音高值相差过大,那么这一首乐曲就会十分不协调,因此大 G 创作乐曲时,同一首乐曲中绝对不会出现两个音符的音高相差大于 k。

大 G 这会儿要创作两首乐曲来取悦小 Q,他希望在里面加入的音符越多越好。请你告诉他,在他即将创作的这两首乐曲中,总共最多能放入多少音符。

注意:每个音符至多只能被放进其中一首乐曲。

Input

第一行两个正整数 n, k。

接下来 n 行每行一个正整数,第 i 行的正整数 a_i 表示第 i 个音符的音高。

Output

输出一个正整数,表示大 G 能在两首乐曲中放入的最多的音符数量。

Examples

Input

10 3
12
17
6
3
18
12
18
14
4
13

Output

7

Input

5 5
11
13
15
6
19

Output

4

Input

6 4
8
4
2
19
5
6

Output

5
Hint

样例 1 解释

第一首乐曲放入音高为 12, 12, 13, 14 的音符,第二首乐曲放入音高为 17, 18, 18 的音符,总共放入 7 个音符,不存在更优解。

数据范围

  • 对于 1 \sim 5 号测试点,n \le 1000;
  • 对于 6 \sim 10 号测试点,n \le 5 \times 10^5。

对于 100\% 的数据,1 \le a_i, k \le 10^9。

提示

把音高从小到大排序后,同一首乐曲能容纳的音符一定是排序后的一个连续段。先用双指针(或二分)求出以每个位置为左端点的最长合法区间长度 c_i,再求后缀最大值,枚举第一段的左端点即可得到答案,复杂度 O(n \log n)。

Source
2024梦熊CSP-J20连测 普及模拟赛16
Tags
题目参数
Time Limit 1 second
Memory Limit 256 MB
提交次数 1
通过次数 1