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;
import java.util.Arrays;

public class c{

    static class SegmentTree{
        int N;
        int data[];
        int index[];

        SegmentTree(int n, int[] set){
            N = 1;
            while(N<n)N*=2;
            data = new int[N*2];
            Arrays.fill(data,-5000);
            index= new int[N*2];
            for(int i=0;i<set.length;++i){
                data[i+N-1]=set[i];
                index[i+N-1]=i;
            }
            for(int i=N-2;i>=0;--i){
                if(data[i*2 +1] > data[i*2  +2]){
                    data[i]=data[i*2+1];
                    index[i]=index[i*2+1];
                }else{
                    data[i]=data[i*2+2];
                    index[i]=index[i*2+2];
                }
            }
        }

        int getMaxIndex(int a,int b,int k,int l,int r){
            if(r<=a || l>=b)return -1;
            if(a<=l && r<=b)return index[k];



            int index1 = getMaxIndex(a, b, 2*k+1, l, (l+r)/2);
            int index2 = getMaxIndex(a, b, 2*k+2, (l+r)/2, r);

            if(index1==-1)return index2;
            if(index2==-1)return index1;
            if(data[N-1 + index1] > data[N-1 + index2])return index1;
            else return index2;
        }

        //[a,b)
        int getMaxIndex(int a, int b){
            return getMaxIndex(a, b, 0, 0, N);
        }

    }

    public static void main(String[] args){
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        boolean[] a = new boolean[n];
        for(int i=0;i<n;++i)a[i]=(scan.nextInt() == 2);

        int set[] = new int[n];
        set[0] = (a[0] ? 1:-1);
        for(int i=1;i<n;++i)set[i] = set[i-1] + (a[i] ? 1:-1);
        SegmentTree st = new SegmentTree(n, set);
        int one[] = new int[n+1];
        int two[] = new int[n+1];
        one[0]=0;
        two[0]=0;
        for(int i=0;i<n;++i){
            one[i+1]=one[i]+(a[i] ? 0:1);
            two[i+1]=two[i]+(a[i] ? 1:0);
        }
        int ans =0;

        //for(int i=0;i<n;++i)System.out.println(st.getMaxIndex(0,i+1));


        for(int i=0;i<n;++i){
            for(int j=i;j<n;++j){
                int index = st.getMaxIndex(i, j+1);
                int num = one[i] + (two[n] - two[j+1]);
                if(a[index])num += two[index+1]-two[i] + (one[j+1] - one[index+1]);
                else num += one[j+1] - one[i];
                ans = Math.max(ans,num);
            }
        }
        System.out.println(ans);

    }
}