1113 - Chụp ảnh cùng thầy Yeh

Tạo bởi: CLB Olympic Tin học HUTECH

Mô tả yêu cầu

Trong ca khúc Lối Nhỏ, rapper Đen Vâu có viết "Kỉ niệm sẽ là thứ duy nhất đi theo anh cả cuộc đời dài". Vì là một Đồng Âm chân chính, thầy Yeh đã quyết định sẽ chụp nhiều hình ảnh nhất có thể cho lớp mà ông đang chủ nhiệm. Và là người cầm máy, ông muốn đảm bảo rằng những bức hình mình chụp phải là oneshot (chụp một lần duy nhất) và xinh đẹp tuyệt vời. Một bức hình xinh đẹp tuyệt vời là khi trong bức ảnh đó độ chênh lệch giữa chiều cao của học sinh cao nhất và học sinh thấp nhất không vượt quá K.

Lớp của ông có N học sinh. Khi các học sinh đã đứng vào vị trí mà chúng thích, học sinh thứ i sẽ có chiều cao là a_i. Bây giờ đây bạn hãy cho thầy Yeh biết ông có thể chụp tối đa bao nhiêu bức hình xinh đẹp tuyệt vời của lớp này nhé.

Dữ liệu vào

  • Dòng thứ nhất gồm hai số nguyên N , K (1 \leq N \leq 5 \times 10^5; 0 \leq K \leq 10^9).
  • Dòng thứ hai gồm N số nguyên a_1, a_2,..., a_N (0 \leq a_i \leq 10^9).

Dữ liệu ra

Số lượng bức hình tối đa mà thầy Yeh có thể chụp.

Ví dụ

Dữ liệu vào Sao chép
4 3
10 5 6 2
Dữ liệu ra Sao chép
5

Gợi ý/Hướng dẫn

Các dãy học sinh thỏa mãn độ chênh lệch giữa học sinh cao nhất và học sinh thất nhấp \leq K:

  • {10} có độ chênh lệch là 0.
  • {5} có độ chênh lệch là 0.
  • {6} có độ chênh lệch là 0.
  • {2} có độ chênh lệch là 0.
  • {5, 6} có độ chênh lệch là 1.
Đăng nhập để làm bài
Thông tin
Giới hạn thời gian 1 giây
Giới hạn bộ nhớ 128 MB