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.*;
import java.io.*;
import java.math.*;

public class MainClass
{	
	public static void main(String[] args)  throws IOException 
	{
		InputReader in = new InputReader(System.in);
		PrintWriter out = new PrintWriter(System.out);
	
		int n=in.nextInt();
		
		
		
		int s1=0,s2=0,s3=0,s4=0;
		
		for(int i=0;i<n;i++)
		{
			int x=in.nextInt();
			if(x==1){s1++;s3++;}
			else
			{s2++;s4++;}
			
			s2=Math.max(s2, s1);

			s3=Math.max(s2, s3);
			s4=Math.max(s3, s4);
			
		}
		
		out.println(s4);
		out.flush();
		out.close();
	}

}
class InputReader{
    private final InputStream stream;
    private final byte[] buf=new byte[1024];
    private int curChar;
    private int numChars;
    public InputReader(InputStream stream){this.stream=stream;}
    public int read()throws IOException{
        if(curChar>=numChars){
            curChar=0;
            numChars=stream.read(buf);
            if(numChars<=0)
                return -1;
        }
        return buf[curChar++];
    }
    public final int nextInt()throws IOException{return (int)nextLong();}
    public final long nextLong()throws IOException{
        int c=read();
        while(isSpaceChar(c)){
            c=read();
            if(c==-1) throw new IOException();
        }
        boolean negative=false;
        if(c=='-'){
            negative=true;
            c=read();
        }
        long res=0;
        do{
            if(c<'0'||c>'9')throw new InputMismatchException();
            res*=10;
            res+=(c-'0');
            c=read();
        }while(!isSpaceChar(c));
        return negative?(-res):(res);
    }
    public final int[] readIntBrray(int size)throws IOException{
        int[] arr=new int[size];
        for(int i=0;i<size;i++)arr[i]=nextInt();
        return arr;
    }
    public final String next()throws IOException{
        int c=read();
        while(isSpaceChar(c))c=read();
        StringBuilder res=new StringBuilder();
        do{
            res.append((char)c);
            c=read();
        }while(!isSpaceChar(c));
        return res.toString();
    }
    public final String nextLine()throws IOException{
        int c=read();
        while(isSpaceChar(c))c=read();
        StringBuilder res=new StringBuilder();
        do{
            res.append((char)c);
            c=read();
        }while(c!='\n'&&c!=-1);
        return res.toString();
    }
    private boolean isSpaceChar(int c){
        return c==' '||c=='\n'||c=='\r'||c=='\t'||c==-1;
    }

}