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.util.Scanner;

public class Main {
public static void main(String[] args) {
	Scanner in = new Scanner(System.in);
    int N = in.nextInt();
    int arr[] = new int[N];
    int one[] = new int[N+1]; // ones[i] 表示到从零开始到i位置有几1
    int two [] = new int [N+1];// 同上.....几个2
    
    for(int i=0;i<N;i++) {
    	arr[i]=in.nextInt();
        
    	one[i+1]=one[i];
        two[i+1]=two[i];
        if(arr[i]==1)
        	one[i+1]++;
        else
        	two[i+1]++;
    }
    int ans=0;
    for(int i=0;i<N;i++) {
    	//计算i位置前面1的个数加上i位置后面2的个数
  ans=Math.max(ans,count(one,0,i)+count(two,i,N));
    
    int d=0;
    for(int j=i+1;j<=N;j++) { //从i位置后面开始
    	if(arr[j-1]==1) {   //如果i位置是1
    		//计算i到j位置上有几个2
    		d=Math.max(d+1, count(two,i,j)+1);
    	}
    	int t = Math.max(d, count(two,i,j));
    	
    	//计算从i位置之前有几个1和i到j位置有几个2和j位置到最后有几个2
    	ans=Math.max(ans, count(one,0,i)+t+count(two,j,N));
    	
    }
    }
    System.out.println(ans);    
}
//返回数组arr中s到l位置有个数字
public static int count(int arr[],int s,int l) {  
	return (arr[l]-arr[s]);
}
}
