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 a1, a2, ..., an.

Little Tommy is among them. He would like to choose an interval [l, r] (1 ≤ l ≤ r ≤ n), then reverse al, al + 1, ..., ar 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 p1, p2, ..., pk, such that p1 < p2 < ... < pk and ap1 ≤ ap2 ≤ ... ≤ apk. The length of the subsequence is k.

Input

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 a1, a2, ..., an (1 ≤ ai ≤ 2, i = 1, 2, ..., n).

Output

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

Examples

Input

4
1 2 1 2


Output

4


Input

10
1 1 2 2 2 1 1 2 2 1


Output

9

Note

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.
	import java.io.*;
	import java.util.*;
	import java.io.BufferedReader;
    import java.math.BigInteger;
    public class Broclock2
    {
    	public static void main(String args[])throws IOException
    	{
    		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    		StringTokenizer st = new StringTokenizer(br.readLine());
    		int n=Integer.parseInt(st.nextToken());
    		int a[]=new int[n];
    		st = new StringTokenizer(br.readLine());
    		int p=0;
    		while (st.hasMoreTokens()) {
    			a[p]=Integer.parseInt(st.nextToken());
    			p++;
    		}
    		solve(n,a);
    	}
    	static void solve(int n,int a[])
        {

                int[][][] fdp = new int[3][n][n];
                int[][][] bdp = new int[3][n][n+1];
                for (int i = 0; i < n; i++) {
                        for (int j = i; j < n; j++) {
                                if(i==j){
                                        if(a[i]==1) fdp[0][i][j] = 1;
                                        else fdp[2][i][j] = 1;
                                        continue;
                                }
                                if(a[j]==1){
                                        fdp[0][i][j] = fdp[0][i][j-1]+1;
                                        fdp[1][i][j] = fdp[1][i][j-1];
                                        fdp[2][i][j] = fdp[2][i][j-1];
                                }
                                else{
                                        fdp[0][i][j] = fdp[0][i][j-1];
                                        fdp[1][i][j] = max(fdp[0][i][j-1],fdp[1][i][j-1])+1;
                                        fdp[2][i][j] = fdp[2][i][j-1]+1;
                                }
                        }
                }
                for (int i = n-1; i >= 0 ; i--) {
                        for (int j = i; j >=0 ; j--) {
                                if(i==j){
                                        if(a[i]==1) bdp[0][i][j] =1 ;
                                        else bdp[2][i][j] = 1;
                                        continue;
                                }
                                if(a[j] == 1){
                                        bdp[0][i][j] = bdp[0][i][j+1]+1;
                                        bdp[1][i][j] = bdp[1][i][j+1];
                                        bdp[2][i][j] = bdp[2][i][j+1];
                                }
                                else{
                                        bdp[0][i][j] = bdp[0][i][j+1];
                                        bdp[1][i][j] = max(bdp[0][i][j+1],bdp[1][i][j+1])+1;
                                        bdp[2][i][j] = bdp[2][i][j+1]+1;
                                }
                        }
                }

                int max_value  = max(fdp[0][0][n-1],max(fdp[1][0][n-1],fdp[2][0][n-1]));
                for (int i = 0; i < n; i++) {
                        for (int j = i; j < n; j++) {
                                int f_left,f_left1,f_left2; // 1 1 , 1 2, 2 2
                                if(i==0){
                                        f_left=f_left1=f_left2=0;
                                }
                                else{
                                        f_left=fdp[0][0][i-1];f_left1 = fdp[1][0][i-1]; f_left2 = fdp[2][0][i-1];
                                }
                                int b_mid = bdp[0][j][i], b_mid1 = bdp[1][j][i], b_mid2 = bdp[2][j][i];
                                int f_right,f_right1,f_right2;
                                if(j==n-1){
                                        f_right=f_right1=f_right2=0;
                                }
                                else {
                                        f_right = fdp[0][j+1][n-1];f_right1 = fdp[1][j+1][n-1]; f_right2 = fdp[2][j+1][n-1];
                                }
                                int first   = f_left + b_mid  + f_right; // 11 11 11
                                int second  = f_left + b_mid  + f_right1;// 11 11 12
                                int third   = f_left + b_mid1 + f_right2;// 11 12 22
                                int fourth  = f_left + b_mid2 + f_right2;// 11 22 22
                                int fifth   = f_left1+ b_mid2 + f_right2;// 12 22 22
                                int sixth   = f_left2+ b_mid2 + f_right2;// 22 22 22
                                max_value = max(max_value,max(first,max(second,max(third,max(fourth,max(fifth,sixth))))));
                        }

                }
                System.out.println(max_value);
        }
        static int max(int a,int b){
                if(a>b) return a;
                return b;
        }
	}