Bắt cóc

Xem PDF

Điểm: 400 (p) Thời gian: 1.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

\(dungde99\) đang có \(n\) buổi hẹn với \(n\) anh trai đỏ Codeforces vào ngày \(a_1, a_2, a_3,\cdots, a_n\) tương ứng (các ngày có thể trùng nhau). Tiếc là \(dungde99\) chỉ được nghỉ vào \(m\) ngày liên tiếp nên cô ấy muốn tranh thủ gặp càng nhiều anh trai đỏ Codeforces càng tốt.

Thế nhưng cuom1999 lại lên kế hoạch bắt đi mất một anh trai của \(dungde99\). Cụ thể là, cuom1999 sẽ tính toán chọn một người anh trai từ danh sách của \(dungde99\) sao cho số anh trai nhiều nhất \(dungde99\) có thể gặp được sau đi bị bắt mất một anh là ít nhất.

Hãy đưa ra số anh trai nhiều nhất \(dungde99\) có thể gặp được theo tính toán của cuom1999. Biết rằng cuom1999 cũng nick đỏ Codeforces nên luôn tìm cách chọn một anh trai tối ưu nhất.

Input

  • Dòng đầu chứa hai số nguyên \(n\), \(m\). Trong đó \(n\) là số buổi hẹn với các anh trai của \(dungde99\), \(m\) là số ngày nghỉ liên tiếp của \(dungde99\).
  • Dòng 2 chứa \(n\) số nguyên \(a_i\) là ngày gặp mặt anh trai thứ \(i\). (các số \(a_i\) được sắp xếp theo thứ tự tăng dần).

Ouput

  • Một dòng duy nhất đưa ra kết quả của bài toán.

Constraints

  • \(1 \leq a_i \leq 10^9\)
  • \(1 \leq m \leq 10^9\)

Scoring

  • Subtask \(1\) (\(10\%\) số điểm): \(1 \leq n \leq 100\)
  • Subtask \(2\) (\(40\%\) số điểm): \(1 \leq n \leq 10^4\)
  • Subtask \(3\) (\(50\%\) số điểm): \(1 \leq n \leq 10^6\)

Example

Test 1

Input
7 5    
1 3 7 10 11 19 20 
Output
2
Note

Ban đầu \(dungde99\) có thể gặp được nhiều nhất \(3\) anh trai ở vị trí \(3,4,5\). Nếu cuom1999 bắt đi một anh trai ở vị trí số \(3\) hoặc \(4\) hoặc \(5\) thì số anh trai gặp được nhiều nhất có thể của \(dungde99\)\(2\).


Bình luận