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.

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$.