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 com.company;
//

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


public class Main {
    static int mod = 1000000007;
    public static void main(String[] args) throws IOException {
        MyScanner sc = new MyScanner(System.in);
        PrintWriter pw = new PrintWriter(System.out);
        C.solve(sc, pw);
        pw.close();
    }

    public static class A {
        static int n, m;
        static long[] a;
        static long[] b;
        public static void solve(MyScanner sc, PrintWriter pw) throws IOException {
            n = sc.nextInt();
            m = sc.nextInt();
            a = new long[n]; b = new long[m];
            for (int i = 0; i < n; i++) {
                a[i] = sc.nextLong();
            }
            for (int i = 0; i < m; i++) {
                b[i] = sc.nextLong();
            }
            Arrays.sort(a);
            Arrays.sort(b);
            List<Long> res = new ArrayList<>();
            if (n == 2){
                if (a[0] * b[0] > a[1] * b[m - 1]) {
                    pw.println(Math.max(a[1] * b[0], a[1] * b[m - 1]));
                } else {
                    pw.println(Math.max(a[0] * b[0], a[0] * b[m - 1]));
                }
                return;
            }
            res.add(a[n-2] * b[0]);
            res.add(a[n-2] * b[m - 1]);
            res.add(a[1] * b[0]);
            res.add(a[1] * b[m - 1]);
            Collections.sort(res);
            pw.println(res.get(res.size() - 1));

        }
    }


    public static class B {
        static int[] lpp = new int[]{1, 0, 0, 0, 1, 0, 1, 0, 2, 1};
        public static void solve(MyScanner sc, PrintWriter pw) throws IOException {
            int k = sc.nextInt();
            if (k > 34) {
                pw.println(-1); return;
            }
            int n8 = k / 2;
            int n6 = k % 2;
            long res = 0;
            for (int i = 0; i < n8; i++) {
                res *= 10; res += 8;
            }
            for (int i = 0; i < n6; i++) {
                res *= 10; res += 6;
            }
            pw.println(res);

        }
    }

    public static class C {
        static int n;

        static int[] arr;
        static int[][][] dp;
        static int[] cnt1;
        static int[] cnt2;
        public static void solve(MyScanner sc, PrintWriter pw) throws IOException {
            n = sc.nextInt();
            arr = new int[n];
            dp = new int[n][n + 1][2];
            cnt1= new int[n + 1];
            cnt2 = new int[n + 1];
            for (int i = 0; i < n; i++) {
                arr[i] = sc.nextInt();
            }
            for (int i = n - 1; i >= 0; i--) {
                for (int j = i; j >= 0; j--) {
                    if (arr[j] == 1){
                        dp[i][j][0] = dp[i][j + 1][0] + 1;
                        dp[i][j][1] = dp[i][j + 1][1];
                    } else {
                        dp[i][j][0] = dp[i][j + 1][0];
                        dp[i][j][1] = Math.max(dp[i][j + 1][1] + 1, dp[i][j + 1][0] + 1);
                    }
                }
            }
            int cnt = 0;
            for (int i = 0; i < n; i++) {
                if (arr[i] == 1) {
                    cnt++; cnt1[i + 1] = cnt;
                }
            }
            cnt = 0;
            for (int i = n - 1; i >=0; i--) {
                if (arr[i] == 2) {
                    cnt++;
                    cnt2[i] = cnt;
                }
            }
            cnt = 0;
            for (int i = 0; i < n; i++) {
                for (int j = i; j < n; j++) {
                    cnt = Math.max(cnt, cnt1[i] + Math.max(dp[j][i][1], dp[j][i][0]) + cnt2[j + 1]);
                }
            }
            pw.println(cnt);
        }
    }

    public static class E {
        static int n;
        static int[] x;
        static int[] y;
        static int[] r;
        public static double dist(int x1, int y1, double x2, double y2) {
            return Math.sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2));
        }

        public static void solve(MyScanner sc, PrintWriter pw) throws IOException {
            n  = sc.nextInt();
            x = new int[n]; y = new int[n]; r = new int[n];
            for (int i = 0; i < n; i++) {
                x[i] = sc.nextInt();
                y[i] = sc.nextInt();
                r[i] = sc.nextInt();
            }
            int[] used = new int[100];
            for (int i = -20; i <= 20; i++) {
                for (int j = -20; j <= 20; j++) {
                    int code = 0;
                    double x2 = (i + 0.0) / 2;
                    double y2 = (j + 0.0) / 2;
                    for (int k = 0; k < n; k++) {
                        double dis = dist(x[k], y[k], x2, y2);
                        if (dis + 1e-6 < r[k]) {
                            code += 1 << k;
                        }
                    }
                    used[code] += 1;
                }
            }
            int cnt = 0;
            for (int i = 0; i < 100; i++) {
                if (used[i] >= 1) {
                    cnt ++;
                }
            }
            pw.println(cnt);
        }
    }


    static class MyScanner {
        StringTokenizer st;
        BufferedReader br;

        public MyScanner(InputStream s){  br = new BufferedReader(new InputStreamReader(s));}

        public MyScanner(FileReader s) throws FileNotFoundException {br = new BufferedReader(s);}

        public String next() throws IOException
        {
            while (st == null || !st.hasMoreTokens())
                st = new StringTokenizer(br.readLine());
            return st.nextToken();
        }

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

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

        public String nextLine() throws IOException {return br.readLine();}

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

        public boolean ready() throws IOException {return br.ready();}
    }
}