Startup

Một startup công nghệ vừa trải qua \(N\) ngày hoạt động. Doanh thu trong ngày thứ \(i\) \((1 \le i \le N)\) được ghi lại là \(A_i\) đô-la.

Quản lý của startup cần chuẩn bị báo cáo để thuyết trình với nhà đầu tư. Anh ta sẽ chọn một số ngày trong số \(N\) ngày này và trình bày biểu đồ cột thể hiện doanh thu của các ngày đã chọn theo thứ tự thời gian.

Để báo cáo gây ấn tượng hơn, anh ta sẽ chọn các ngày sao cho điểm ấn tượng là cao nhất.

Nếu anh ta chọn \(m\) ngày \((1 \le m \le N)\) với chỉ số \(p_1, p_2, \dots, p_m\) \((1 \le p_1 < p_2 < \dots < p_m \le N)\) thì điểm ấn tượng được tính như sau:

• Ban đầu, ngày đầu tiên trong danh sách luôn được tính là một kỷ lục mới.
• Với mỗi ngày tiếp theo trong danh sách, nếu doanh thu hôm đó lớn hơn tất cả các ngày trước đó (trong danh sách đã chọn), thì điểm ấn tượng tăng thêm \(1\).

Nói cách khác, điểm ấn tượng chính là số lần xuất hiện một mức doanh thu kỷ lục mới trong chuỗi ngày đã chọn.

Để bài thuyết trình không gượng ép, Minh chỉ chọn các ngày thoả đồng thời hai quy tắc sau:

• Bắt buộc phải bao gồm ngày cuối cùng: \(p_m = N\).
• Khoảng cách giữa hai ngày liên tiếp không vượt quá \(D\): với mọi \(j\) \((1 \le j \le m-1)\), ta có \(p_{j+1} - p_j \le D\).

Hãy tính điểm ấn tượng lớn nhất có thể đạt được.

Input

• Dòng đầu chứa hai số nguyên \(N\) và \(D\) (\(D \le N \le 3 \times 10^5\)).
• Dòng thứ hai chứa \(N\) số nguyên \(A_1, A_2, \dots, A_N\) --- doanh thu từng ngày.

Output

• In ra một số nguyên duy nhất --- điểm ấn tượng tối đa theo các quy tắc trên.

Example

6 6
1 5 2 4 6 3

4

Scoring

• Có \(14\%\) số điểm ứng với \(N \leq 20\).
• Có \(14\%\) số điểm ứng với \(N \leq 400\).
• Có \(20\%\) số điểm ứng với \(N \leq 7000\).
• Có \(12\%\) số điểm ứng với \(D = 1\).
• Có \(40\%\) số điểm ứng không có ràng buộc bổ sung nào khác.