Chứng khoán

Giá bán của một cổ phiếu được xem là ổn định trong một khoảng thời gian nếu chênh lệch giữa giá cao nhất và giá thấp nhất trong khoảng đó không vượt quá một ngưỡng \(T\) cho trước.

Cho dãy giá bán của một cổ phiếu trong \(N\) phiên giao dịch: \(G_1, G_2, \dots, G_N\).
Một đoạn liên tiếp \([l, r]\) được gọi là ổn định nếu

Yêu cầu. Hãy tìm độ dài lớn nhất của một đoạn liên tiếp ổn định.

Input

• Dòng đầu chứa hai số nguyên \(T\) và \(N\) \((0 \le T \le 2\cdot 10^9,\ 1 \le N \le 3\cdot 10^6)\).
• Dòng thứ hai chứa \(N\) số nguyên \(G_1, G_2, \dots, G_N\) \((0 \le G_i \le 2\cdot 10^9)\).

Output

• In ra một số nguyên là độ dài lớn nhất của một đoạn liên tiếp ổn định.

Scoring

• (20%) \(1 < N \le 10\,000\);
• (30%) \(10\,000 < N \le 500\,000\);
• (50%) \(500\,000 < N \le 3\,000\,000\).

Input

%
5 10
5 7 9 20 15 13 20 12 11 1

Output

%
3

Notes

Trong ví dụ, đoạn ổn định dài nhất có độ dài \(3\), ví dụ đoạn \([1,3]\) có \(\max=9\), \(\min=5\) nên chênh lệch là \(4 \le 5\).
Không tồn tại đoạn ổn định nào có độ dài \(4\).