Giải bài trực tuyến

Cho 1 dãy số nguyên a[1], a[2], …, a[N]. Bạn có thể cộng hoặc trừ mỗi phần tử đi một lượng tối đa là D (dãy số sau khi cộng/trừ có thể xuất hiện số âm hoặc số thực). Hãy tìm độ dài của dây con không giảm dài nhất của dãy số, nếu cộng/trừ các phân tử một cách tối ưu.

Lưu ý: dãy con của dãy số là dãy số a[x[1]], a[x[2]], ..., a[x[k]] (k là một số nguyên) sao cho 1 ≤ x[1] < x[2] < ... < x[k] ≤ N.

Input

• Dòng đầu tiên chứa 2 số nguyên N và D.
• Dòng thứ 2 chứa N số nguyên a[1], a[2], …, a[N], các số được cách nhau bởi ít nhất 1 dấu cách.

Output

• Một dòng duy nhất là độ dài dãy con không giảm dài nhất trong phương án tối ưu.

Giới hạn

• 0 < N ≤ 1000.
• 0 ≤ D ≤ 10^9.
• 0 ≤ a[i] ≤ 10^9.
• Trong 30% số test, D = 0.

Example

Input:
4 1
6 4 3 2

Output:
3
Giải thích: Có thể biến đổi dãy thành 6 3 3 3.