(doantang.*)

Cho một dãy số nguyên \(a\) gồm \(n\) phần tử \(a_{1},a_{2},...,a_{N}\). Một đoạn con của dãy số gồm các phần tử liên tiếp nhau trong dãy, độ dài đoạn con là số lượng phần tử trong đoạn con đó.

Yêu cầu: Hãy tìm đoạn con dài nhất trong dãy \(a\) thỏa mãn tính chất sau:

+ Đoạn con đó chỉ gồm các phần tử có giá trị chẵn hoặc chỉ gồm các phần tử có giá trị lẻ.

+ Các phần tử có giá trị tăng dần.

Dữ liệu vào:

+ Dòng thứ nhất: Số nguyên \(n\) \((1 \leq \ n\ \leq \ 10^{6})\) là số lượng phần tử của dãy \(a\).

+ Dòng thứ hai: \(n\) số nguyên \(a_{1},a_{2},...,a_{N}(\left| a_{i} \right| \leq 10^{9}\) với \(1 \leq i \leq n)\). Các số cách nhau một khoảng trắng.

Kết quả:

+ Ghi một số nguyên duy nhất là độ dài của đoạn con tìm được.

Ví dụ:

Input	Output
9 2 1 3 5 5 6 3 7 6	3

Ràng buộc:

+ Có 80% số test tương ứng với 80% số điểm của bài thỏa mãn \(n \leq 5000;\)

+ Có 20% số test tương ứng với 20% số điểm của bài thỏa mãn \(5000 < n \leq 10^{6}.\)