Bóng rổ

Xem PDF
Tất cả bài nộp
Các bài nộp tốt nhất
Tác giả:
Siquy3001
Dạng bài
Điểm: 100 (p) Thời gian: 1.5s Bộ nhớ: 1G Input: bàn phím Output: màn hình

tk21quytransi là một vận động viên bóng rổ chuyên nghiệp. Một ngày tk21quytransi muốn đếm lại xem hiện tại mình đang có bao nhiêu chiếc giày. Sau khi kiểm tra, tk21quytransi còn \(n\) chiếc giày, chiếc thứ \(i\) có màu độ sáng \(s_i\) (\(1 \leq i \leq n\)), độ sáng càng lớn thì màu càng sáng.
Mỗi trận đấu tk21quytransi lấy ra một đôi sử dụng, sau trận đấu đó, anh tháo giày và tặng lại cho các fan hâm mộ của mình. Hai chiếc giày mà anh chọn phải có độ sáng chênh lệch nhau không quá \(d\), tức là hai chiếc giày thứ \(i\) và \(j\) (\(i ≠ j\)) có thể được chọn nếu \(\lvert s_i - s_j \rvert \leq d\).
Em hãy viết chương trình tính giúp tk21quytransi xem với \(n\) chiếc giày hiện có anh ấy sẽ chơi được tối đa bao nhiêu trận đấu.

Input

  • Dòng đầu tiên chứa số tự nhiên \(n\) và \(d\) (\(n \leq 10^6, d \leq 10^9\)).
  • Dòng tiếp theo chứa \(n\) só tự nhiên \(s_1, s_2, ..., s_n\) (\(s_i \leq 10^9\)).

Output

  • In ra số trận đấu tối đa tk21quytransi có thể chơi được.

Scoring

  • Subtask \(1\) (\(25\%\) số điểm): \(d = 0, a_i \le 10 ^ {6}\)
  • Subtask \(2\) (\(25\%\) số điểm): \(d = 0\)
  • Subtask \(3\) (\(25\%\) số điểm): \(n \le 10 ^ {3}\)
  • Subtask \(4\) (\(25\%\) số điểm): \(n \le 10 ^ {6}\)

Example

Test 1
Input 
5 1
4 5 1 3 2
Output 
2
Note
  • Trận đấu thứ nhất tk21quytransi mang chiếc giày thứ 3 và chiếc giày thứ 5, độ sáng chêch lệch là \(\lvert 1 - 2 \rvert = 1 \leq 1\).
  • Trận đấu thứ hai tk21quytransi mang chiếc giày thứ 1 vào chiếc giày thứ 4, độ sáng chêch lệch là \(\lvert 4 - 3 \rvert = 1 \leq 1\).
  • Lúc này tk21quytransi chỉ còn 1 chiếc giày nên không thể tham gia thi đấu tiếp được.

Bình luận