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 a_1, a_2, ..., a_{n}.

Little Tommy is among them. He would like to choose an interval [l, r] (1 ≤ l ≤ r ≤ n), then reverse a_{l}, a_{l} + 1, ..., a_{r} 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 p_1, p_2, ..., p_{k}, such that p_1 < p_2 < ... < p_{k} and a_{p}_1 ≤ a_{p}_2 ≤ ... ≤ a_{p}_{k}. 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 a_1, a_2, ..., a_{n} (1 ≤ a_{i} ≤ 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.

Difficulty: competition

Starter code:

Solutions:
n = int(input())
*A, = list(map(int, input().split()))

seq = []
cur = 1; cnt = 0
for a in A:
    if cur == a:
        cnt += 1
    else:
        seq.append(cnt)
        cur = a; cnt = 1
if cnt > 0:
    seq.append(cnt)
ans = max(seq)

l = len(seq)
dp = [[0]*4 for i in range(l+1)]
for i in range(l):
    one = i % 2 #12
    s = seq[i]
    for j in range(4):
        dp[i+1][j] = max(dp[i+1][j], dp[i][j])
        if not one: # 2
            if j % 2 == 0:
                dp[i+1][j] = max(dp[i+1][j], dp[i][j] + s)
            else:
                if j == 1:
                    dp[i+1][j+1] = max(dp[i+1][j+1], dp[i][j] + s)
        else: # 1
            if j % 2 == 1:
                dp[i+1][j] = max(dp[i+1][j], dp[i][j] + s)
            else:
                dp[i+1][j+1] = max(dp[i+1][j+1], dp[i][j] + s)
#    print(dp[i+1])
print(max(dp[l]))





a = [0] * 4
input()
for n in map(int, input().split()):
  if n == 1:
    a[0] += 1
    a[2] = max(a[1] + 1, a[2] + 1)
  else:
    a[1] = max(a[0] + 1, a[1] + 1)
    a[3] = max(a[2] + 1, a[3] + 1)
print(max(a))

input()
a = list(map(int, input().split()))

p1,p2,p3,p4=0,0,0,0

for n in a:
    if n == 1:
        p1 += 1
        p3 = max(p3 + 1, p2 + 1)
    else:
        p2 = max(p2 + 1, p1 + 1)
        p4 = max(p4 + 1, p3 + 1)
print(max(p1,p2,p3,p4))

n = int(input())
a = list(map(int, input().split()))

d = [0 for _ in range(4)]

for val in a:
    if val == 1:
        d[0] += 1
        d[2] = max(d[2] + 1, d[1] + 1)
    else:
        d[1] = max(d[1] + 1, d[0] + 1)
        d[3] = max(d[3] + 1, d[2] + 1)
print(max(d))
        


n=int(input())
a=list(map(int,input().split()))
t1,t2,t3,t4=0,0,0,0
for i in range(len(a)):
    if a[i]==1:
        t1+=1
        t3=max(t3+1,t2+1)
    else:
        t2=max(t2+1,t1+1)
        t4=max(t4+1,t3+1)
print(max(t1,t2,t3,t4))





##////////////////      //////        ///////      //             ///////     //  //   //
##////          //    ///   ///     ///    ///     //            ///  ///     ////     //
##////    ////       ///     ///   ///      ///    //           /////////     ////     ///////
##////     /////    ///       /// ///        ///   //          ///    ///     ////     //   //
##//////////////     ///////////   ///////////     //////     ///     ///     //  //   //   //





n=int(input())

a,ab,aba,abab=0,0,0,0

b=[int(x) for x in input().split()]

for x in b:

    if x==1:

        a+=1

        aba+=1

    else:

        ab+=1

        abab+=1

    ab=max(a,ab)

    aba=max(aba,ab)

    abab=max(abab,aba)

print(abab)





# Made By Mostafa_Khaled


#fek mikoni aslan lozoomi dare kasi tu in donya dustet dashtet bashe ?!
#age are chera tanhayi ?!!
#age na chera namordi ?!!!
DP = [0] * 4
input()
for x in map(int, input().split()):
    if x == 1 :
        DP[0] += 1
        DP[2] += 1
    else :
        DP[1] += 1
        DP[3] += 1
    for j in range ( 1 , 4 ) :
        DP[j] = max ( DP[j] , DP[j-1] )
print (DP[3]) 

R = lambda: map(int, input().split())
n = int(input())
dp = [0] * 5
for x in R():
    if x == 1:
        dp[1], dp[3] = dp[1] + 1, max(dp[3], dp[2]) + 1
    else:
        dp[2], dp[4] = max(dp[1], dp[2]) + 1, max(dp[3], dp[4]) + 1
print(max(dp))

a = [0] * 4
input()
for n in map(int, input().split()):
  if n == 1:
    a[0] += 1
    a[2] = max(a[1] + 1, a[2] + 1)
  else:
    a[1] = max(a[0] + 1, a[1] + 1)
    a[3] = max(a[2] + 1, a[3] + 1)

print(max(a))
        


n = int(input())
A = list(map(int, input().split()))
one = [0]
two = [0]
for i in A:
    one.append(one[-1])
    two.append(two[-1])
    if i == 1:
        one[-1] += 1
    else:
        two[-1] += 1
rdp1 = [[1] * n for _ in range(n)]
for l in range(n):
    for r in range(l + 1, n):
        if A[r] == 2:
            rdp1[l][r] = rdp1[l][r - 1] + 1
        else:
            if rdp1[l][r - 1] == one[r] - one[l]:
                rdp1[l][r] = rdp1[l][r - 1] + 1
            else:
                rdp1[l][r] = rdp1[l][r - 1]
rdp2 = [[1] * n for _ in range(n)]
for l in range(n):
    for r in range(l + 1, n):
        if A[r] == 1:
            rdp2[l][r] = rdp2[l][r - 1] + 1
        else:
            if rdp2[l][r - 1] == two[r] - two[l]:
                rdp2[l][r] = rdp2[l][r - 1] + 1
            else:
                rdp2[l][r] = rdp2[l][r - 1]
dp = [0] * n
dp[0] = 1
for i in range(1, n):
    if A[i] == 2:
        dp[i] = dp[i - 1] + 1
    else:
        if dp[i - 1] == one[i]:
            dp[i] = dp[i - 1] + 1
        else:
            dp[i] = dp[i - 1]
    dp[i] = max(dp[i], rdp2[0][i])
    for j in range(i):
        if rdp1[0][j] == one[j + 1]:
            dp[i] = max(dp[i], rdp1[0][j] + rdp2[j + 1][i])
        dp[i] = max(dp[i], rdp1[0][j] + two[i + 1] - two[j + 1])
print(dp[-1])


n = int(input())
A = list(map(int, input().split()))
one = [0]
two = [0]
for i in A:
    one.append(one[-1])
    two.append(two[-1])
    if i == 1:
        one[-1] += 1
    else:
        two[-1] += 1
rdp1 = [[1] * n for _ in range(n)]
rdp2 = [[1] * n for _ in range(n)]
for l in range(n):
    for r in range(l + 1, n):
        if A[r] == 2:
            rdp1[l][r] = rdp1[l][r - 1] + 1
        else:
            if rdp1[l][r - 1] == one[r] - one[l]:
                rdp1[l][r] = rdp1[l][r - 1] + 1
            else:
                rdp1[l][r] = rdp1[l][r - 1]
        if A[r] == 1:
            rdp2[l][r] = rdp2[l][r - 1] + 1
        else:
            if rdp2[l][r - 1] == two[r] - two[l]:
                rdp2[l][r] = rdp2[l][r - 1] + 1
            else:
                rdp2[l][r] = rdp2[l][r - 1]
dp = [0] * n
dp[0] = 1
for i in range(1, n):
    if A[i] == 2:
        dp[i] = dp[i - 1] + 1
    else:
        if dp[i - 1] == one[i]:
            dp[i] = dp[i - 1] + 1
        else:
            dp[i] = dp[i - 1]
    dp[i] = max(dp[i], rdp2[0][i])
    for j in range(i):
        if rdp1[0][j] == one[j + 1]:
            dp[i] = max(dp[i], rdp1[0][j] + rdp2[j + 1][i])
        dp[i] = max(dp[i], rdp1[0][j] + two[i + 1] - two[j + 1])
print(dp[-1])


# import sys 
# sys.stdin = open('input.txt', 'r')  
# sys.stdout = open('output.txt', 'w')

n = int(input())
a = list(map(int,input().split()))

count = [0]*4

for i in range(n):
	if (a[i] == 1):
		count[0] += 1
		count[2] = max(count[1]+1,count[2]+1)
	else:
		count[1] = max(count[1]+1,count[0]+1)
		count[3] = max(count[3]+1,count[2]+1)

print(max(count))

def solve(lst):
    a = b = c = d = 0
    for i in range(len(lst)):
        if lst[i] == 1:
            a += 1
            c = max(b, c) + 1
        else:
            b = max(a, b) + 1
            d = max(c, d) + 1
    return max(a, b, c, d)

n = input()
lst = list(map(int, input().split()))
print(solve(lst))


import sys
import math
from collections import defaultdict
n=int(sys.stdin.readline())
arr=list(map(int,sys.stdin.readline().split()))
pre=[0]
cnt1,cnt2=0,0
last1,last2=0,0
for i in range(n):
    if arr[i]==1:
        cnt1+=1
        #pre.append(cnt1)
        x=max(last1+1,0)
        pre.append(x)
        last1=x
    else:
        #cnt2+=1
        x=max(last1+1,last2+1)
        pre.append(x)
        last2=x
suf=[0 for _ in range(n+1)]
#cnt1,cnt2=0,0
last1,last2=0,0
for i in range(n-1,-1,-1):
    if arr[i]==1:
        #cnt1+=1
        x=max(last1+1,last2+1)
        suf[i]=x
        last1=x
    else:
        #cnt2+=1
        x=last2+1
        suf[i]=x
        last2=x
ans=max(max(pre),max(suf))
#print(pre,'pre')
#print(suf,'suf')
#print(ans,'ans')
for i in range(1,n+1):
    cnt1,cnt2=0,0
    last1,last2=0,0
    for j in range(i,n+1):
        if arr[j-1]==1:
            x=max(last1+1,last2+1)
            last1=x
            ans=max(pre[i-1]+x+suf[j],ans)
        else:
            x=last2+1
            last2=x
            ans=max(pre[i-1]+x+suf[j],ans)
print(ans)


n = int(input())
a = list(map(int, input().split()))
pref = [0] * (n + 1)
for i in range(n):
	pref[i + 1] = pref[i] + (1 if a[i] == 1 else 0)
suf = [0] * (n + 1)
for i in reversed(range(n)):
	suf[i] = suf[i + 1] + (1 if a[i] == 2 else 0)
dp = [0, 0, 0, 0]
for i in range(n):
	new_dp = [max(dp[i], dp[i - 1]) if i > 0 else dp[i] for i in range(4)]
	if a[i] == 1:
		new_dp[0] += 1
		new_dp[2] += 1
	else:
		new_dp[1] += 1
		new_dp[3] += 1
	dp = new_dp
print(max(max([pref[i] + suf[i] for i in range(n + 1)]), max(dp)))

n = int(input())
a = list(map(int, input().split()))
dp = [0] * 4
for j in range(n):
	dp = [dp[i] if i == 0 else max(dp[i], dp[i - 1]) for i in range(4)]
	dp = [dp[i] + (1 if i % 2 == a[j] - 1 else 0) for i in range(4)]
print(max(dp))

# https://codeforces.com/contest/933/problem/A
import sys
reader = (s.rstrip() for s in sys.stdin)
input = reader.__next__
# do magic here

n = int(input())
arr = list(map(int, input().split()))
dp = [[0 for x in range(n)] for y in range(4)]

if arr[0] == 1:
    dp[0][0] = 1
else:
    dp[1][0] = 1

for i in range(1, n):
    if arr[i] == 1:
        dp[0][i] = dp[0][i-1] + 1
    else:
        dp[0][i] = dp[0][i-1]

for i in range(1, n):
    if arr[i] == 2:
        dp[1][i] = max(dp[1][i-1] + 1, dp[0][i-1] + 1)
    else:
        dp[1][i] = dp[1][i-1]

for i in range(1,n):
    if arr[i] == 1:
        dp[2][i] = max([dp[2][i-1] + 1, dp[1][i-1] + 1, dp[0][i-1] + 1])
    else:
        dp[2][i] = dp[2][i-1]

for i in range(1,n):
    if arr[i] == 2:
        dp[3][i] = max([dp[3][i-1] + 1, dp[2][i-1] + 1, dp[1][i-1] + 1, dp[0][i-1] + 1])
    else:
        dp[3][i] = dp[3][i-1]
# print(dp)
ans = max([dp[2][n-1],dp[1][n-1],dp[0][n-1],dp[3][n-1]])
print(ans)


#t=int(input())
t=1
for _ in range(t):
    n=int(input())
    l=list(map(int,input().split()))
    dp=[[0 for j in range(4)] for i in range(n)]
    p1=[0]*(n+1)
    p2=[0]*(n+1)
    for i in range(n):
        p1[i+1]+=p1[i]
        p2[i+1]+=p2[i]
        if l[i]==1:
            p1[i+1]+=1
        else:
            p2[i+1]+=1
    if l[0]==1:        
        dp[0][0]=1
    else:
        dp[0][1]=1
    for i in range(1,n):
        for j in range(i-1,-1,-1):
            if l[i]==1:
                dp[i][0]=p1[i+1]
                dp[i][1]=max(dp[j][1],dp[i][1])
                if dp[j][1]!=0:
                    dp[i][2]=max(dp[j][1]+1,dp[j][2]+1,dp[i][2])
                else:
                    dp[i][2]=max(dp[j][2]+1,dp[i][2])
                dp[i][3]=max(dp[j][2],dp[i][3])
            else:
                dp[i][0]=max(dp[j][0],dp[i][0])
                if dp[j][0]!=0:
                    dp[i][1]=max(dp[j][1]+1,dp[j][0]+1,dp[i][1])
                else:
                    dp[i][1]=max(dp[j][1]+1,dp[i][1])
                dp[i][2]=dp[j][2]
                if dp[j][2]!=0:
                    dp[i][3]=max(dp[j][3]+1,dp[j][2]+1,dp[i][3])
                else:
                    dp[i][3]=max(dp[j][3]+1,dp[i][3])
    maxi=0
    for i in range(n):
        for j in range(4):
            maxi=max(maxi,dp[i][j])
    print(maxi)