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.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.UncheckedIOException;
import java.io.Closeable;
import java.io.Writer;
import java.io.OutputStreamWriter;
import java.lang.reflect.Array;
import java.util.Arrays;


public class water {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        FastInput input = new FastInput(inputStream);
        FastOutput out = new FastOutput(outputStream);
        int n= input.scanInt();
        int a[]=new int [n];
        int b[]=new int [n];
        int len=0,poi=1;
        int x= input.scanInt();
        a[0]=x;
        for(int i=1;i<n;i++){
            a[i]= input.scanInt();
            if(a[i]==1&&x==1){
                poi++;
            }
            else if(a[i]==2&&x==2){
                poi++;
            }
            else if(a[i]==2){
                b[len++]=poi;
                poi=1;
                x=2;
            }
            else if(a[i]==1){
                b[len++]=poi;
                poi=1;
                x=1;
            }
        }
        b[len++]=poi;
        int max[]=new int [len];
        int []c=new int [n];
        int mach=0;

        if(len%2==0&&a[0]==1){
            for(int i=0;i<len;i+=2){
                mach+=b[i];
                c[i]=mach;
            }
            mach=0;
            for(int i=len-1;i>=0;i-=2){
                mach+=b[i];
                c[i]=mach;
            }
        }
        else if(len%2==0&&a[0]==2){
            for(int i=1;i<len;i+=2){
                mach+=b[i];
                c[i]=mach;
            }
            mach=0;
            for(int i=len-2;i>=0;i-=2){
                mach+=b[i];
                c[i]=mach;
            }
        }
        else if(a[0]==2){
            for(int i=1;i<len;i+=2){
                mach+=b[i];
                c[i]=mach;
            }
            mach=0;
            for(int i=len-1;i>=0;i-=2){
                mach+=b[i];
                c[i]=mach;
            }
        }
        else{
            for(int i=0;i<len;i+=2){
                mach+=b[i];
                c[i]=mach;
            }
            mach=0;
            for(int i=len-2;i>=0;i-=2){
                mach+=b[i];
                c[i]=mach;
            }
        }
        int mas=0;
        for(int i=0;i<len;i++){
            if(i<len-1)
                max[i]=c[i]+c[i+1];
            else
                max[i]=c[i];
            if(max[i]>mas)mas=max[i];
        }
        if(a[0]==1){
            for(int i=0;i<len;i+=2){
                int ma=0;
                int one=0;
                if(i>0){
                    one=b[i-1];
                }
                int mac=0,mad=one,macx=0,madx=one;
                for(int j=i+2;j<len;j+=2){
                    mac+=b[j]-b[j-1];
                    if(mac>macx)macx=mac;
                }
                for(int k=i-3;k>=0;k-=2){
                    mad+=b[k]-b[k+1];
                    if(mad>madx) madx=mad;
                }
                ma=madx+macx;
                if(i<len-1)
                    max[i]=c[i]+c[i+1]+ma;
                else
                    max[i]=c[i]+ma;
                if(max[i]>mas)mas=max[i];
            }
        }
        else{
            for(int i=1;i<len;i+=2){
                int ma=0;
                int one=0;
                if(i>0){
                    one=b[i-1];
                }
                int mac=0,mad=one,macx=0,madx=one;
                for(int j=i+2;j<len;j+=2){
                    mac+=b[j]-b[j-1];
                    if(mac>macx)macx=mac;
                }
                for(int k=i-3;k>=0;k-=2){
                    mad+=b[k]-b[k+1];
                    if(mad>madx) madx=mad;
                }
                ma=madx+macx;
                if(i<len-1)
                    max[i]=c[i]+c[i+1]+ma;
                else
                    max[i]=c[i]+ma;
                if(max[i]>mas)mas=max[i];
            }
        }
         System.out.println(" "+mas);


    }

    static class FastInput {
        private final InputStream is;
        private StringBuilder defaultStringBuf = new StringBuilder(1 << 13);
        private byte[] buf = new byte[1 << 13];
        private int bufLen;
        private int bufOffset;
        private int next;
        public FastInput(InputStream is) {
            this.is = is;
        }
        private int read() {
            while (bufLen == bufOffset) {
                bufOffset = 0;
                try {
                    bufLen = is.read(buf);
                } catch (IOException e) {
                    bufLen = -1;
                }
                if (bufLen == -1) {
                    return -1;
                }
            }
            return buf[bufOffset++];
        }
        public void skipBlank() {
            while (next >= 0 && next <= 32) {
                next = read();
            }
        }
        public String next() {
            return readString();
        }
        public int scanInt() {
            int sign = 1;
            skipBlank();
            if (next == '+' || next == '-') {
                sign = next == '+' ? 1 : -1;
                next = read();
            }
            int val = 0;
            while (next >= '0' && next <= '9') {
                val = val * 10 + next - '0';
                next = read();
            }
            return (sign*val);
        }

        public String readString(StringBuilder builder) {
            skipBlank();
            while (next > 32) {
                builder.append((char) next);
                next = read();
            }
            return builder.toString();
        }

        public String readString() {
            defaultStringBuf.setLength(0);
            return readString(defaultStringBuf);
        }

    }
    static class FastOutput implements AutoCloseable, Closeable, Appendable {
        private StringBuilder cache = new StringBuilder(1 << 20);
        private final Writer os;

        public FastOutput append(CharSequence csq) {
            cache.append(csq);
            return this;
        }

        public FastOutput append(CharSequence csq, int start, int end) {
            cache.append(csq, start, end);
            return this;
        }

        public FastOutput(Writer os) {
            this.os = os;
        }

        public FastOutput(OutputStream os) {
            this(new OutputStreamWriter(os));
        }

        public FastOutput append(char c) {
            cache.append(c);
            return this;
        }

        public FastOutput append(String c) {
            cache.append(c);
            return this;
        }
        public FastOutput append(int c) {
            cache.append(c);
            return this;
        }
        public FastOutput println(int c) {
            return append(c).println();
        }
        public FastOutput println(String c) {
            return append(c).println();
        }

        public FastOutput println() {
            //cache.append(System.lineSeparator());
//            flush();
            return this;
        }

        public FastOutput flush() {
            try {
                os.append(cache);
                os.flush();
                cache.setLength(0);
            } catch (IOException e) {
                throw new UncheckedIOException(e);
            }
            return this;
        }

        public void close() {
            flush();
            try {
                os.close();
            } catch (IOException e) {
                throw new UncheckedIOException(e);
            }
        }

        public String toString() {
            return cache.toString();
        }

    }


}




