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: MEDIUM_HARD
Tags: Dynamic programming
Skill types: Dynamic programming

Starter code:

Solutions:
from math import *
import re
n = int(input())
a = list(map(int, input().split()))
(d1, d2, d3, d4) = ([0] * n, [0] * n, [0] * n, [0] * n)
d1[0] = d3[0] = 1 if a[0] == 1 else 0
d2[0] = d4[0] = 1 if a[0] == 2 else 0
for i in range(1, n):
	d1[i] = d1[i - 1]
	d2[i] = d2[i - 1]
	d3[i] = d3[i - 1]
	d4[i] = d4[i - 1]
	if a[i] == 1:
		d1[i] = d1[i - 1] + 1
		d3[i] = max(d3[i - 1], d2[i - 1]) + 1
	if a[i] == 2:
		d2[i] = max(d2[i - 1], d1[i - 1]) + 1
		d4[i] = max(d4[i - 1], d3[i - 1]) + 1
print(max(max(d1), max(d2), max(d3), max(d4)))


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
	s = seq[i]
	for j in range(4):
		dp[i + 1][j] = max(dp[i + 1][j], dp[i][j])
		if not one:
			if j % 2 == 0:
				dp[i + 1][j] = max(dp[i + 1][j], dp[i][j] + s)
			elif j == 1:
				dp[i + 1][j + 1] = max(dp[i + 1][j + 1], dp[i][j] + s)
		elif 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(max(dp[l]))


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, 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)


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))


import sys

def input():
	return sys.stdin.buffer.readline().rstrip()
n = int(input())
a = list(map(int, input().split()))
ans = max(a.count(1), a.count(2))
prefix = [0] * (n + 10)
suffix = [0] * (n + 10)
for i in range(n):
	if a[i] == 1:
		prefix[i + 1] = 1
a.reverse()
for i in range(n):
	if a[i] == 2:
		suffix[i + 1] = 1
a.reverse()
for i in range(n):
	prefix[i + 1] += prefix[i]
	suffix[i + 1] += suffix[i]
INF = 1 << 60
a.reverse()
ans = -INF
for l in range(n):
	max_case_1 = 0
	max_case_2 = 0
	for r in range(l, n):
		if a[r] == 1:
			max_case_1 += 1
		elif a[r] == 2:
			max_case_2 = max(max_case_2, max_case_1) + 1
		K = max(max_case_1, max_case_2)
		ans = max(ans, K + prefix[n - 1 - r] + suffix[l])
print(ans)


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
		elif 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
		elif 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
	elif 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()))
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))


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))


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])


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))


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
		x = max(last1 + 1, 0)
		pre.append(x)
		last1 = x
	else:
		x = max(last1 + 1, last2 + 1)
		pre.append(x)
		last2 = x
suf = [0 for _ in range(n + 1)]
(last1, last2) = (0, 0)
for i in range(n - 1, -1, -1):
	if arr[i] == 1:
		x = max(last1 + 1, last2 + 1)
		suf[i] = x
		last1 = x
	else:
		x = last2 + 1
		suf[i] = x
		last2 = x
ans = max(max(pre), max(suf))
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)


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)


import sys
reader = (s.rstrip() for s in sys.stdin)
input = reader.__next__
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]
ans = max([dp[2][n - 1], dp[1][n - 1], dp[0][n - 1], dp[3][n - 1]])
print(ans)


import os
import sys
import math
from io import BytesIO, IOBase
from fractions import Fraction
import collections
from itertools import permutations
from collections import defaultdict
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
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))


import sys
input = sys.stdin.readline
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))


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))


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))


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()


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()))
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))