Chuyển động uốn lượn

Cho một dãy gồm $n$ số nguyên $a_1,a_2,\dots ,a_n$, trong đó mỗi phần tử chỉ nhận giá trị $1$ hoặc $2$.

Bạn được phép chọn đúng một đoạn $[l,r]$ (với $1\le l\le r\le n$) rồi đảo ngược thứ tự các phần tử trong đoạn đó, tức là $a_l,a_{l+1},\dots ,a_r$ trở thành $a_r,a_{r-1},\dots ,a_l$.

Sau khi thực hiện phép đảo ngược, hãy tính độ dài dãy con không giảm dài nhất của dãy mới. Bạn cần chọn đoạn $[l,r]$ sao cho độ dài này lớn nhất có thể.

Một dãy con không giảm là một dãy các chỉ số $p_1<p_2<\dots <p_k$ sao cho $a_{p_1}\le a_{p_2}\le \dots \le a_{p_k}$. Độ dài của dãy con là $k$.

Dữ liệu vào

• Dòng đầu chứa số nguyên $n$, độ dài của dãy.
• Dòng thứ hai chứa $n$ số nguyên $a_1,a_2,\dots ,a_n$.

Dữ liệu ra

• In ra một số nguyên duy nhất là độ dài lớn nhất có thể của dãy con không giảm sau khi đảo ngược đúng một đoạn.

Ràng buộc

• $1\le n\le 2000$
• $1\le a_i\le 2$

Ví dụ