KDIFF - Trồng hoa

Giới hạn
  • Thời gian: 0.4s
  • Bộ nhớ: 1536MB
  • Mã nguồn: 50000 bytes

Ghi chú: Các bài VNOI đã được chuyển qua VNOJ (Thông báo). Đề bài trên VNOI và vn.spoj.com sẽ không được cập nhật nữa. Một số đề bài không chính xác sẽ chỉ được cập nhật trên VNOJ. Bạn vẫn có thể tìm kiếm đề bài trên VNOI.

Link đọc đề trên VNOJ

Pirate là một người rất yêu hoa. Anh ấy trồng một luống hoa trước cửa nhà mình. Luống hoa được chia thành các ô đất, mỗi ô đất trồng một bông hoa. Tuy nhiên, vì đang bị đau chân nên Pirate ấy không thể chăm sóc luống hoa một cách hoàn hảo nhất. Kết quả là các bông hoa của anh có xấu đẹp không đều nhau.

Để cải thiện tình hình, Pirate quyết định chỉ để lại hai khóm hoa rời nhau, mỗi khóm gồm một số các bông hoa đứng liên tiếp nhau. Để ngôi nhà của mình trông thật xinh đẹp, hai khóm hoa kia phải được chọn lựa kỹ càng. Anh dùng đôi mắt thẩm mỹ tinh tường của mình (gọi là "sắc kế") để đánh giá độ xinh đẹp của các bông hoa, được thể hiện bằng các số nguyên không âm. Căn cứ vào đó, một khóm hoa đạt tiêu chuẩn khi và chỉ khi chệnh lệch độ xinh đẹp giữa hai bông hoa bất kì trong khóm không quá một giá trị cho trước. Pirate muốn hai khóm hoa có càng nhiều bông hoa càng tốt. Bạn hãy giúp anh ấy xác định xem có thể chọn được nhiều nhất bao nhiêu bông nhé.

Input

  • Dòng 1: Hai số nguyên N - số bông hoa trên luống hoa, K - chênh lệch độ xinh đẹp tối đa của hai bông hoa bất kì trong một khóm.
  • N dòng tiếp theo: Mỗi dòng là một số nguyên thể hiện độ xinh đẹp của một bông hoa.

Output

  • Một số nguyên duy nhất là số bông hoa được chọn của hai khóm hoa.

Giới hạn

  • 1 ≤ N ≤ 3 * 10 5 .
  • 30% số test có 1 ≤ N ≤ 30.
  • 50% số test có 1 ≤ N ≤ 10 3 .
  • Các số trong dữ liệu vào đều là số nguyên không âm không quá 10 9 .

Example 

Input:
5 2
1 
3 
2 
5 
4

Output:
5

Giải thích: hai khóm hoa được chọn là (1, 2, 3) và (4, 5).
Input:
5 2
1 
3 
5 
2 
4

Output:
4

Giải thích: hai khóm hoa được chọn là (1, 2) và (4, 5).

  • Người up: khanhptnk