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.BufferedWriter;
import java.io.IOException;
import java.io.InputStream;
import java.io.OutputStreamWriter;
import java.math.BigDecimal;
import java.math.MathContext;
import java.math.RoundingMode;


import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Map.Entry;
import java.util.PriorityQueue;
import java.util.Random;
import java.util.TreeSet;


public final class CF_462_D1_A{

	static boolean verb=true;
	static void log(Object X){if (verb) System.err.println(X);}
	static void log(Object[] X){if (verb) {for (Object U:X) System.err.print(U+" ");System.err.println("");}}
	static void log(int[] X){if (verb) {for (int U:X) System.err.print(U+" ");System.err.println("");}}
	static void log(int[] X,int L){if (verb) {for (int i=0;i<L;i++) System.err.print(X[i]+" ");System.err.println("");}}
	static void log(long[] X){if (verb) {for (long U:X) System.err.print(U+" ");System.err.println("");}}

	static void logWln(Object X){if (verb) System.err.print(X);}
	static void info(Object o){	System.out.println(o);}
	static void output(Object o){outputWln(""+o+"\n");	}
	static void outputWln(Object o){try {out.write(""+ o);} catch (Exception e) {}}


	static long mod=1000000007;
	static long MX=1000000000000000001L;

	// Global vars
	static BufferedWriter out;
	static InputReader reader;

	static long powerMod(long b,long e,long m){
		long x=1;
		while (e>0) {
			if (e%2==1)
				x=(b*x)%m;
			b=(b*b)%m;
			e=e/2;
		}
		return x; 
	}



	static void process() throws Exception {


		out = new BufferedWriter(new OutputStreamWriter(System.out));
		reader=new InputReader(System.in);

		int n=reader.readInt();
		int[] a=new int[n];
		int[] b=new int[n];
		for (int i=0;i<n;i++) {
			a[i]=reader.readInt();

		}
		int[][][][] inc=new int[2][2][n][n];
		int[][][][] dec=new int[2][2][n][n];
		for (int i=0;i<n;i++){
			int x=a[i]-1;
			inc[x][x][i][i]=1;

			for (int j=i+1;j<n;j++){
				for (int f=0;f<2;f++)
					for (int e=0;e<=f;e++) {
						inc[e][f][i][j]=inc[e][f][i][j-1];

					}
				int y=a[j]-1;
				for (int f=0;f<=y;f++)
					for (int e=0;e<=f;e++){
						inc[e][y][i][j]=Math.max(inc[e][y][i][j],inc[e][f][i][j-1]+1);
					}

			}

		}


		for (int i=0;i<n;i++){
			int x=a[i]-1;
			dec[x][x][i][i]=1;

			for (int j=i+1;j<n;j++){
				for (int f=0;f<2;f++)
					for (int e=0;e<=f;e++) {
						dec[f][e][i][j]=dec[f][e][i][j-1];

					}
				int z=a[j]-1;
				for (int e=z;e<2;e++)
					for (int f=e;f<2;f++)
						dec[f][z][i][j]=Math.max(dec[f][z][i][j],dec[f][e][i][j-1]+1);
			}



		}

		int best=0;

		for (int i=0;i<n;i++)
			for (int j=i;j<n;j++){
				for (int e=0;e<2;e++)
					for (int ee=e;ee<2;ee++)
						for (int f=ee;f<2;f++)
							for (int ff=f;ff<2;ff++)
								for (int g=ff;g<2;g++)
									for (int gg=g;gg<2;gg++){
				
				
				
								int tm=0;
								int t1=0;
								int t2=0;
								int t3=0;
								if (i>0)
									t1=inc[e][ee][0][i-1];
								if (j+1<n)
									t2=inc[g][gg][j+1][n-1];
								//log(f+" "+e+" "+i+" "+j+" // "+(n-1));
								t3=dec[ff][f][i][j];
								tm=t1+t2+t3;
								if (tm>best) {
									best=tm;
									//log("tm:"+tm+" // "+t1+" "+t2+" "+t3+" i:"+i+" j:"+j);

								}
							}
			}

		output(best);


		try {
			out.close();
		}
		catch (Exception EX){}


	}


	public static void main(String[] args) throws Exception {
		process();

	}

	static final 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;
		}

		private int read() throws IOException {
			if (curChar >= numChars) {
				curChar = 0;
				numChars = stream.read(buf);
				if (numChars <= 0) {
					return -1;
				}
			}
			return buf[curChar++];
		}


		public final String readString() 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 int readInt() throws IOException {
			int c = read();
			boolean neg=false;
			while (isSpaceChar(c)) {
				c = read();
			}
			char d=(char)c;
			//log("d:"+d);
			if (d=='-') {
				neg=true;
				c = read();
			}
			int res = 0;
			do {
				res *= 10;
				res += c - '0';
				c = read();
			} while (!isSpaceChar(c));
			//log("res:"+res);
			if (neg)
				return -res;
			return res;

		}

		public final long readLong() throws IOException {
			int c = read();
			boolean neg=false;
			while (isSpaceChar(c)) {
				c = read();
			}
			char d=(char)c;
			//log("d:"+d);
			if (d=='-') {
				neg=true;
				c = read();
			}
			long res = 0;
			do {
				res *= 10;
				res += c - '0';
				c = read();
			} while (!isSpaceChar(c));
			//log("res:"+res);
			if (neg)
				return -res;
			return res;

		}




		private boolean isSpaceChar(int c) {
			return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
		}
	}


}