Codeforces Round 462 (Div. 1) |
---|

Finished |

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

dp

*1800

No tag edit access

The problem statement has recently been changed. View the changes.

×
A. A Twisty Movement

time limit per test

1 secondmemory limit per test

256 megabytesinput

standard inputoutput

standard outputA 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*_{p1} ≤ *a*_{p2} ≤ ... ≤ *a*_{pk}. 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.

Codeforces (c) Copyright 2010-2023 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Mar/31/2023 21:42:30 (h2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|