Chuyển động xoắn

Cho dãy số $a_1,a_2,\dots ,a_n$ gồm $n$ phần tử, mỗi phần tử có giá trị $1$ hoặc $2$.

Bạn được phép chọn đúng một đoạn $[l,r]$ ($1\le l\le r\le n$) và đảo ngược các phần tử trong đoạn đó (tức biến $a_l,a_{l+1},\dots ,a_r$ thành $a_r,a_{r-1},\dots ,a_l$). Sau khi thực hiện thao tác này, hãy tìm độ dài lớn nhất của một dãy con không giảm của dãy thu được.

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

Bạn phải thực hiện phép đảo (bắt buộc chọn một đoạn, $l$ có thể bằng $r$).

Dữ liệu vào

• Dòng đầu chứa số nguyên $n$ — độ dài dãy.
• Dòng thứ hai chứa $n$ số nguyên $a_1,a_2,\dots ,a_n$, mỗi số là $1$ hoặc $2$.

Dữ liệu ra

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

Ràng buộc

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

Ví dụ