Problem
Petya bé nhỏ thích chấm. Mới đây, mẹ anh ấy đã cho anh ấy n điểm nằm trên đường thẳng OX. Petya tự hỏi có bao nhiêu cách chọn ba điểm khác nhau sao cho khoảng cách giữa hai điểm xa nhất không vượt quá d.
Lưu ý rằng thứ tự của các điểm trong bộ ba đã chọn không quan trọng.
Đầu vào
Dòng đầu tiên chứa hai số nguyên: n và d (1 ≤ n ≤ 105; 1 ≤ d ≤ 10< sup>9). Dòng tiếp theo chứa n số nguyên x1, x2, ..., xn, modulo không quá 109 — tọa độ x của các điểm được trao cho Petya.
Tọa độ của các điểm trong đầu vào được đảm bảo là tăng dần.
Đầu ra
In một số nguyên duy nhất — số bộ ba điểm mà khoảng cách giữa hai điểm xa nhất không vượt quá d.
Vui lòng không sử dụng trình xác định %lld để đọc hoặc ghi các số 64-bit trong C++. Bạn nên sử dụng các luồng cin, cout hoặc bộ xác định %I64d.
| Đầu vào |
Đầu ra |
|
4 3
1 2 3 4
|
4 |
|
4 2
-3 -2 -1 0
|
2 |
|
5 19
1 10 20 30 50
|
1 |
Trong ví dụ đầu tiên, bất kỳ ba điểm khác nhau nào cũng phù hợp với chúng tôi.
Trong ví dụ thứ hai, chỉ có 2 bộ ba phù hợp với chúng ta: {-3, -2, -1} và {-2, -1, 0}.
Trong ví dụ thứ ba, một bộ ba phù hợp với chúng ta: {1, 10, 20}.