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.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

/**
 * Created by prituladima on 5/23/18.
 */
public class TwistyMovement {

    private void solve() throws IOException {

        int n = nextInt();
        int[] a = nextArr(n);

        int[][][] fdp = new int[3][n][n];
        int[][][] bdp = new int[3][n][n+1];
        for (int i = 0; i < n; i++) {
            for (int j = i; j < n; j++) {
                if(i==j){
                    if(a[i]==1) fdp[0][i][j] = 1;
                    else fdp[2][i][j] = 1;
                    continue;
                }
                if(a[j]==1){
                    fdp[0][i][j] = fdp[0][i][j-1]+1;
                    fdp[1][i][j] = fdp[1][i][j-1];
                    fdp[2][i][j] = fdp[2][i][j-1];
                }
                else{
                    fdp[0][i][j] = fdp[0][i][j-1];
                    fdp[1][i][j] = max(fdp[0][i][j-1],fdp[1][i][j-1])+1;
                    fdp[2][i][j] = fdp[2][i][j-1]+1;
                }
            }
        }
        for (int i = n-1; i >= 0 ; i--) {
            for (int j = i; j >=0 ; j--) {
                if(i==j){
                    if(a[i]==1) bdp[0][i][j] =1 ;
                    else bdp[2][i][j] = 1;
                    continue;
                }
                if(a[j] == 1){
                    bdp[0][i][j] = bdp[0][i][j+1]+1;
                    bdp[1][i][j] = bdp[1][i][j+1];
                    bdp[2][i][j] = bdp[2][i][j+1];
                }
                else{
                    bdp[0][i][j] = bdp[0][i][j+1];
                    bdp[1][i][j] = max(bdp[0][i][j+1],bdp[1][i][j+1])+1;
                    bdp[2][i][j] = bdp[2][i][j+1]+1;
                }
            }
        }

        int max_value  = max(fdp[0][0][n-1],max(fdp[1][0][n-1],fdp[2][0][n-1]));
        for (int i = 0; i < n; i++) {
            for (int j = i; j < n; j++) {
                int f_left,f_left1,f_left2; // 1 1 , 1 2, 2 2
                if(i==0){
                    f_left=f_left1=f_left2=0;
                }
                else{
                    f_left=fdp[0][0][i-1];f_left1 = fdp[1][0][i-1]; f_left2 = fdp[2][0][i-1];
                }
                int b_mid = bdp[0][j][i], b_mid1 = bdp[1][j][i], b_mid2 = bdp[2][j][i];
                int f_right,f_right1,f_right2;
                if(j==n-1){
                    f_right=f_right1=f_right2=0;
                }
                else {
                    f_right = fdp[0][j+1][n-1];f_right1 = fdp[1][j+1][n-1]; f_right2 = fdp[2][j+1][n-1];
                }
                int first   = f_left + b_mid  + f_right; // 11 11 11
                int second  = f_left + b_mid  + f_right1;// 11 11 12
                int third   = f_left + b_mid1 + f_right2;// 11 12 22
                int fourth  = f_left + b_mid2 + f_right2;// 11 22 22
                int fifth   = f_left1+ b_mid2 + f_right2;// 12 22 22
                int sixth   = f_left2+ b_mid2 + f_right2;// 22 22 22
                max_value = max(max_value,max(first,max(second,max(third,max(fourth,max(fifth,sixth))))));
            }

        }
        System.out.println(max_value);

    }


    int max(int a,int b){
        if(a>b) return a;
        return b;
    }
















    public static void main(String[] args) {
        new TwistyMovement().run();
    }

    StringTokenizer tokenizer;
    BufferedReader reader;
    PrintWriter writer;

    public void run() {
        try {
            reader = new BufferedReader(new InputStreamReader(System.in));
            tokenizer = null;
            writer = new PrintWriter(System.out);
            solve();
            reader.close();
            writer.close();
        } catch (Exception e) {
            e.printStackTrace();
            System.exit(1);
        }
    }

    int nextInt() throws IOException {
        return Integer.parseInt(nextToken());
    }

    long nextLong() throws IOException {
        return Long.parseLong(nextToken());
    }

    double nextDouble() throws IOException {
        return Double.parseDouble(nextToken());
    }

    String nextToken() throws IOException {
        while (tokenizer == null || !tokenizer.hasMoreTokens()) {
            tokenizer = new StringTokenizer(reader.readLine());
        }
        return tokenizer.nextToken();
    }

    int[] nextArr(int size) throws NumberFormatException, IOException {
        int[] arr = new int[size];
        for (int i = 0; i < size; i++)
            arr[i] = nextInt();
        return arr;
    }

    long[] nextArrL(int size) throws NumberFormatException, IOException {
        long[] arr = new long[size];
        for (int i = 0; i < size; i++)
            arr[i] = nextLong();
        return arr;
    }

    double[] nextArrD(int size) throws NumberFormatException, IOException {
        double[] arr = new double[size];
        for (int i = 0; i < size; i++)
            arr[i] = nextDouble();
        return arr;
    }

}