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.
/* package codechef; // don't place package name! */

import java.util.*;
import java.lang.*;
import java.io.*;

/* Name of the class has to be "Main" only if the class is public. */
public class Codechef
{
    long MOD = 1000000007L;
    int INF = 1000000001;
    
    public class Obj implements Comparable<Obj>{
        public int start;
        public int end;
        
        public Obj(int start_, int end_){
            this.start = start_;
            this.end = end_;

        }
        
        public int compareTo(Obj other){
            if (other.start == this.start){
                return this.end - other.end;
            }
            return this.start - other.start;
        }

    }
    
    int[] dx = new int[]{-1, 0, 1, 0, -1, 1, 1, -1};
    int[] dy = new int[]{0, 1, 0, -1, 1, 1, -1, -1};
    
	public static void main (String[] args) throws java.lang.Exception
	{
		// your code goes here
        Codechef cf = new Codechef();
        cf.Solve();
	}
	public void Solve(){
        MyScanner sc = new MyScanner();
        int n = sc.nextInt();
        int[][] dp11 = new int[n+2][n+2];
        int[][] dp12 = new int[n+2][n+2];
        int[][] dp22 = new int[n+2][n+2];
        int[][] dd11 = new int[n+2][n+2];
        int[][] dd12 = new int[n+2][n+2];
        int[][] dd22 = new int[n+2][n+2];
        int[] arr = new int[n+2];
        
        for (int i = 1; i <= n; ++i){
            arr[i] = sc.nextInt();
        }
        
        for (int i = 1; i <= n; ++i){
            for (int j = i; j <= n; ++j){
                if (arr[j] == 1){
                    dp11[i][j] = Math.max(dp11[i][j-1] + 1, dp11[i][j]);
                    dp12[i][j] = dp12[i][j-1];
                    dp22[i][j] = dp22[i][j-1];
                }else{
                    dp12[i][j] = Math.max(dp11[i][j-1] + 1, dp12[i][j]);
                    dp12[i][j] = Math.max(dp12[i][j], dp12[i][j-1] + 1);
                    dp22[i][j] = Math.max(dp22[i][j-1] + 1, dp22[i][j]);
                    dp11[i][j] = dp11[i][j-1];
                }
            }
        }
        
        for (int i = n; i >= 1; --i){
            for (int j = i; j >= 1; --j){
                if (arr[j] == 1){
                    dd11[j][i] = Math.max(dd11[j+1][i] + 1, dd11[j][i]);
                    dd12[j][i] = dd12[j+1][i];
                    dd22[j][i] = dd22[j+1][i];
                }else{
                    dd12[j][i] = Math.max(dd11[j+1][i] + 1, dd12[j][i]);
                    dd12[j][i] = Math.max(dd12[j+1][i] + 1, dd12[j][i]);
                    dd22[j][i] = Math.max(dd22[j+1][i] + 1, dd22[j][i]);
                    dd11[j][i] = dd11[j+1][i];
                }
            }
        }
        
        int best = 0;
        // System.out.println(dd12[3][7]);
        int[] res = new int[7];
        for (int i = 1; i <= n; ++i){
            for (int j = i; j <= n; ++j){
                res[0] = dp11[1][i-1] + dd11[i][j] + dp11[j+1][n];
                res[1] = dp11[1][i-1] + dd11[i][j] + dp12[j+1][n];
                res[2] = dp11[1][i-1] + dd11[i][j] + dp22[j+1][n];
                res[3] = dp11[1][i-1] + dd12[i][j] + dp22[j+1][n];
                res[4] = dp11[1][i-1] + dd22[i][j] + dp22[j+1][n];
                res[5] = dp12[1][i-1] + dd22[i][j] + dp22[j+1][n];
                res[6] = dp22[1][i-1] + dd22[i][j] + dp22[j+1][n];
                for (int k = 0; k < 7; ++k){
                    best = Math.max(best, res[k]);
                }
                // System.out.println(i + " " + j + " best: " + best);
            }
        }
        System.out.println(best);
	}
	

	//-----------PrintWriter for faster output---------------------------------
   public static PrintWriter out;
      
   //-----------MyScanner class for faster input----------
   public static class MyScanner {
      BufferedReader br;
      StringTokenizer st;
 
      public MyScanner() {
         br = new BufferedReader(new InputStreamReader(System.in));
      }
 
      String next() {
          while (st == null || !st.hasMoreElements()) {
              try {
                  st = new StringTokenizer(br.readLine());
              } catch (IOException e) {
                  e.printStackTrace();
              }
          }
          return st.nextToken();
      }
 
      int nextInt() {
          return Integer.parseInt(next());
      }
 
      long nextLong() {
          return Long.parseLong(next());
      }
 
      double nextDouble() {
          return Double.parseDouble(next());
      }
 
      String nextLine(){
          String str = "";
      try {
         str = br.readLine();
      } catch (IOException e) {
         e.printStackTrace();
      }
      return str;
      }

   }
}
