Dãy số \(b_{1},b_{2},\ldots,b_{m}\) được gọi là dãy tăng giảm khi và chỉ khi tồn tại một vị trí \(i\ (1 < i < m)\) sao cho \(b_{1} < b_{2} < \ldots < b_{i} > b_{i + 1} > \ldots > b_{m}\)

Yêu cầu: Cho một dãy gồm \(n\) số, hãy tìm dãy con liên tiếp dài nhất là dãy tăng giảm.

Dữ liệu vào:

+ Dòng đầu tiên ghi số nguyên dương \(n\ (n \leq 10^{6})\)

+ Dòng thứ hai ghi lần lượt \(n\) số nguyên \(a_{1},a_{2},\ldots,a_{n}\ (\left| a_{i} \right| \leq 10^{9})\)

Kết quả:

+ Ghi một số nguyên duy nhất cho biết độ dài của dãy tăng giảm dài nhất tìm được

Ví dụ:

Input	Output
9 5 1 3 5 4 2 6 8 4	5

Ràng buộc:

+ Có 50% số test tương ứng 50% số điểm có \(n \leq 2000\);

+ Có 50% số test còn lại tương ứng 50% số điểm không có ràng buộc gì thêm.