Trồng hoa

Tác giả:

Dạng bài

Điểm: 400 (p) Thời gian: 1.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

Pirate là một người rất yêu hoa. Anh ấy trồng một luống hoa trước cửa nhà mình. Luống hoa được chia thành các ô đất, mỗi ô đất trồng một bông hoa. Tuy nhiên, vì đang bị đau chân nên Pirate ấy không thể chăm sóc luống hoa một cách hoàn hảo nhất. Kết quả là các bông hoa của anh có xấu đẹp không đều nhau.

Để cải thiện tình hình, Pirate quyết định chỉ để lại hai khóm hoa rời nhau, mỗi khóm gồm một số các bông hoa đứng liên tiếp nhau. Để ngôi nhà của mình trông thật xinh đẹp, hai khóm hoa kia phải được chọn lựa kỹ càng. Anh dùng đôi mắt thẩm mỹ tinh tường của mình (gọi là "sắc kế") để đánh giá độ xinh đẹp của các bông hoa, được thể hiện bằng các số nguyên không âm. Căn cứ vào đó, một khóm hoa đạt tiêu chuẩn khi và chỉ khi chệnh lệch độ xinh đẹp giữa hai bông hoa bất kì trong khóm không quá một giá trị cho trước. Pirate muốn hai khóm hoa có càng nhiều bông hoa càng tốt. Bạn hãy giúp anh ấy xác định xem có thể chọn được nhiều nhất bao nhiêu bông nhé.

Input

Dòng 1: Hai số nguyên \(N\) - số bông hoa trên luống hoa, \(K\) - chênh lệch độ xinh đẹp tối đa của hai bông hoa bất kì trong một khóm.
\(N\) dòng tiếp theo: Mỗi dòng là một số nguyên thể hiện độ xinh đẹp của một bông hoa.

Output

Một số nguyên duy nhất là số bông hoa được chọn của hai khóm hoa.

Scoring

\(1≤ N≤ 3 × 10^5\).
Subtask \(1\) (\(30\%\) số điểm): \(1≤ N≤ 30\).
Subtask \(2\) (\(50\%\) số điểm): \(1≤ N≤ 10^3\).
Các số trong dữ liệu vào đều là số nguyên không âm không quá \(10^9\).

Example

Test 1

Input

Output

Note

Hai khóm hoa được chọn là (1, 2, 3) và (4, 5).

Test 2

Input

Output

Note

Hai khóm hoa được chọn là (1, 2) và (4, 5).

Bình luận

2

volantuan0908 11:08 p.m. 12 Tháng 10, 2021

ở ví dụ 2 sao không chọn khóm 1 (1,2,3) được ạ? mọi ptu bất kì nào chênh lệch cũng không quá 2 mà;-;?