Thành phố Gloaming (Hoàng hôn) nổi tiếng với đường dẫn vào công viên thành phố. Các bức tượng tuyệt đẹp theo chủ đề thần thoại Hy lạp – La mã đặt dọc theo con đường thẳng có một sức hút không cưỡng được với mọi khách du lịch. Còn khi những tia nắng cuối cùng trong ngày miễn cưỡng rời khỏi bầu trời thì sương mù dày đặc, như một tấm voan trắng mềm mại từ từ rũ xuống. Bây giờ đứng cách quá r mét là đã không nhìn thấy mặt nhau và các bức tượng trở thành nơi lý tưởng cho các đôi nam nữ thanh niên hẹn hò.
James Bond cần gặp gấp 2 điệp viên nội tuyến của mình để nhận các mật báo khẩn. Không muốn 2 người này nhìn thấy nhau, Bond hẹn gặp mỗi người ở một bức tượng sao cho khoảng cách giữa chúng lớn hơn r. Trên đường có n bức tượng, bức tượng thứ i ở vị trí cách đầu con đường di mét i = 1 ÷ n, 1 ≤ d1< d2 < . . .< dn ≤ ~10^9~.
Yêu cầu: Hãy xác định James Bond có bao nhiêu cách chọn địa điểm.
Dữ liệu vào:
Dòng đầu tiên chứa 2 số nguyên n và r (1 ≤ n ≤ 3×105, 1 ≤ r ≤ ~10^9~). Dòng thứ 2 chứa n số nguyên d1, d2, . . ., dn. Kết quả: một số nguyên là số cách chọn địa điểm tìm được.
Ràng buộc:
Có ½ số test tương ứng điểm có n ≤ ~10^4~ Có ½ số test tương ứng điểm có 10^4 < n ≤ 3×10^5
Ví dụ
Inp:
4 4
1 3 5 8
Out:
2
Bình luận
làm sao vậy