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 sys
import math
input = sys.stdin.readline
from functools import cmp_to_key;

def pi():
    return(int(input()))
def pl():
    return(int(input(), 16))
def ti():
    return(list(map(int,input().split())))
def ts():
    s = input()
    return(list(s[:len(s) - 1]))
def invr():
    return(map(int,input().split()))
mod = 998244353;
f = [];
def fact(n,m):
    global f;
    f = [1 for i in range(n+1)];
    f[0] = 1;
    for i in range(1,n+1):
        f[i] = (f[i-1]*i)%m;

def fast_mod_exp(a,b,m):
    res = 1;
    while b > 0:
        if b & 1:
            res = (res*a)%m;
        a = (a*a)%m;
        b = b >> 1;
    return res;

def inverseMod(n,m):
    return fast_mod_exp(n,m-2,m);

def ncr(n,r,m):
    if r == 0: return 1;
    return ((f[n]*inverseMod(f[n-r],m))%m*inverseMod(f[r],m))%m;

def main():
    A();

def D():
    [n,m,k] = ti();
    w = [[] for i in range(n)];
    for i in range(n):
        w[i] = ts();

    mn = [[0 for j in range(k+1)] for i in range(n+1)];
    for i in range(1,n+1):
        for j in range(k+1):
            c = 0;
            st,en = -1,-1;
            for x in range(m):
                if w[i-1][x] == '1':
                    if c == j and st == -1: st = x;
                    if c < j: c += 1;
                    if c == j: en = x;
            mn[i][j] = en-st+1 if st != -1 and en != -1 else 0;
            st,en = -1,-1;
            c = 0;
            for x in range(m-1,-1,-1):
                if w[i-1][x] == '1':
                    if c == j and st == -1: st = x;
                    if c < j: c += 1;
                    if c == j: en = x;
            if st != -1 and en != -1 >= 0:
                mn[i][j] = min(mn[i][j], st-en+1);

    dp = [[9999999999999999 for j in range(k+1)] for i in range(n+1)];
    for i in range(k+1):
        dp[0][i] = 0;
    for i in range(1,n+1):
        for j in range(k+1):
            for x in range(k+1):
                if j-x >= 0:
                    dp[i][j] = min(dp[i][j], dp[i-1][j-x]+mn[i][x]);

    print(dp[n][k]);


def A():
    n,a = pi(),ti();
    dp = [[0 for j in range(n)] for i in range(4)];
    for i in range(4):
        for j in range(n):
            if i == 0:
                if a[j] == 1: dp[i][j] = dp[i][j-1]+1 if j != 0 else 1;
                else: dp[i][j] = dp[i][j-1] if j != 0 else 0;
                continue;
            if i == 1:
                if a[j] == 2: dp[i][j] = max(dp[i-1][j-1]+1,dp[i][j-1]+1) if j != 0 else 1;
                else: dp[i][j] = dp[i][j-1] if j != 0 else 0;
                continue;
            if i == 2:
                if a[j] == 1: dp[i][j] = max(dp[i-1][j-1]+1,dp[i][j-1]+1) if j != 0 else 1;
                else: dp[i][j] = dp[i][j-1] if j != 0 else 0;
                continue;
            if i == 3:
                if a[j] == 2: dp[i][j] = max(dp[i-1][j-1]+1,dp[i][j-1]+1) if j != 0 else 1;
                else: dp[i][j] = dp[i][j-1] if j != 0 else 0;
    print(max(dp[0][n-1],dp[1][n-1],dp[2][n-1],dp[3][n-1]));
    

main();