A Twisty Movement，用dp。注意别读错题。reverse这个词，不是将某一个区间的值1变2,2变1，而是翻转这个区间。详见本文具体内容。

# 题目

A. A Twisty Movement

# 限制

time limit per test: 1 second
memory limit per test: 256 megabytes
input: standard input
output: standard output

# 描述

A dragon symbolizes wisdom, power and wealth. On Lunar New Year’s Day, people model a dragon with bamboo strips and clothes, raise them with rods, and hold the rods high and low to resemble a flying dragon.
A performer holding the rod low is represented by a $1$, while one holding it high is represented by a $2$. Thus, the line of performers can be represented by a sequence $a_1, a_2, …, a_n$.
Little Tommy is among them. He would like to choose an interval $[l, r] (1 \le l \le r \le n)$, then reverse $a_l, a_{l+1}, …, a_r$ so that the length of the longest non-decreasing subsequence of the new sequence is maximum.
A non-decreasing subsequence is a sequence of indices $p_1, p_2, …, p_k$, such that $p_1 < p_2 < … < p_k$ and $a_{p1} \le a_{p2} \le … \le a_{pk}$. The length of the subsequence is $k$.

# 输入格式

The first line contains an integer $n (1 \le n \le 2000)$, denoting the length of the original sequence.
The second line contains n space-separated integers, describing the original sequence $a_1, a_2, …, a_n$ $(1 \le a_i \le 2, i = 1, 2, …, n)$.

# 输出格式

Print a single integer, which means the maximum possible length of the longest non-decreasing subsequence of the new sequence.

# 提示

In the first example, after reversing $[2, 3]$, the array will become $[1, 1, 2, 2]$, where the length of the longest non-decreasing subsequence is 4.
In the second example, after reversing $[3, 7]$, the array will become $[1, 1, 1, 1, 2, 2, 2, 2, 2, 1$], where the length of the longest non-decreasing subsequence is 9.

# 思路

dp[0][i]代表前i个字符内1…的子序列最长的长度是多少。
dp[1][i]代表前i个字符内1…2…的子序列的最长的长度是多少。
dp[2][i]代表前i个字符内1…2…1…的子序列的最长的长度是多少。
dp[3][i]代表前i个字符内1…2…1…2…的子序列的最长的长度是多少。