Biến đổi khí hậu là vấn đề quan trọng và Johnny hiểu điều đó. Anh muốn phân tích dữ liệu nhiệt độ lịch sử để tìm một dãy con tăng thật dài, qua đó thuyết phục những người chưa tin.

Dữ liệu gồm nhiệt độ \(t_i\) trong \(n\) ngày liên tiếp. Dãy con tăng là dãy các phần tử có chỉ số tăng nghiêm ngặt và giá trị cũng tăng nghiêm ngặt.

Để làm dãy con dài hơn, Johnny được chọn một đoạn ngày không rỗng và một số nguyên \(d\) (\(-x\le d\le x\)), rồi cộng \(d\) vào nhiệt độ của tất cả các ngày trong đoạn đó. Có thể chọn \(d=0\).

Hãy tìm độ dài lớn nhất của dãy con tăng dài nhất có thể đạt được sau thao tác.

Dữ liệu vào

Dòng đầu chứa hai số nguyên \(n,x\) (\(1\le n\le200000\), \(0\le x\le10^9\)), lần lượt là số ngày và giới hạn trị tuyệt đối của mức thay đổi.

Dòng thứ hai chứa \(n\) số nguyên \(t_1,t_2,\ldots,t_n\) (\(1\le t_i\le10^9\)), là nhiệt độ của các ngày.

Dữ liệu ra

In độ dài lớn nhất có thể của dãy con tăng.

Ví dụ

8 10
7 3 5 12 2 7 3 4

5

Giải thích

Có thể chọn đoạn ngày \([2,3]\) và \(d=-5\). Dãy nhiệt độ khi đó là \((7,-2,0,12,2,7,3,4)\); một dãy con tăng dài nhất là \((-2,0,2,3,4)\), có độ dài \(5\).

Phân nhóm

1. \(5\) điểm: \(n,x\le10\).
2. \(10\) điểm: \(n,x\le50\).
3. \(13\) điểm: \(n\le1000\).
4. \(10\) điểm: \(x=0\).
5. \(20\) điểm: \(x\le5\) và \(n\le50000\).
6. \(17\) điểm: \(x=10^9\).
7. \(25\) điểm: Không có ràng buộc bổ sung.