CF933A.A Twisty Movement

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 ≤ l ≤ r ≤ 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__p_1 ≤ _a__p_2 ≤ ... ≤ a__p__k. The length of the subsequence is k.

龙象征着智慧、力量与财富。在农历新年当天，人们用竹条和布料制作龙形道具，以长杆支撑，并通过上下挥舞长杆来模拟飞龙腾跃的姿态。

持杆位置较低的表演者用数字 1 表示，持杆位置较高的表演者用数字 2 表示。因此，整列表演者可表示为一个序列 $a_1,\,a_2,\,\dots,\,a_n$。

小汤米是其中一员。他希望选定一个区间 $[l,\,r]$（满足 $1\,\le\,l\,\le\,r\,\le\,n$），然后将子数组 $a_l,\,a_{l+1},\,\dots,\,a_r$ 进行翻转，使得新序列中最长非递减子序列的长度达到最大。

非递减子序列是指一组下标 $p_1,\,p_2,\,\dots,\,p_k$，满足 $p_1\,<\,p_2\,<\,\dots\,<\,p_k$ 且 $a_{p_1}\,\le\,a_{p_2}\,\le\,\dots\,\le\,a_{p_k}$。该子序列的长度为 $k$。

The first line contains an integer n (1 ≤ n ≤ 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 ≤ a__i ≤ 2, i = 1, 2, ..., n).

第一行包含一个整数 $n$（$1 \leq n \leq 2000$），表示原始序列的长度。

第二行包含 $n$ 个用空格分隔的整数，描述原始序列 $a_1, a_2, \dots, a_n$（$1 \leq a_i \leq 2$，其中 $i = 1, 2, \dots, 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.

在第一个例子中，将子数组 $[2, 3]$ 反转后，数组变为 $[1, 1, 2, 2]$，此时最长非递减子序列的长度为 4。

在第二个例子中，将子数组 $[3, 7]$ 反转后，数组变为 $[1, 1, 1, 1, 2, 2, 2, 2, 2, 1]$，此时最长非递减子序列的长度为 9。