题目描述

Farmer John is arranging his $N$ cows in a line to take a photo ($1 \leq N \leq 50$). The height of the $i$th cow in sequence is $a(i)$, and Farmer John thinks it would make for an aesthetically pleasing photo if the cow lineup has a large increasing subsequence of cows by height.

To recall, a subsequence is a subset $a(i_1), a(i_2), \ldots, a(i_k)$ of elements from the cow sequence, found at some series of indices $i_1 < i_2 < \ldots < i_k$. We say the subsequence is increasing if $a(i_1) \leq a(i_2) \leq \ldots \leq a(i_k)$.

FJ would like there to be a long increasing subsequence within his ordering of the cows. In order to ensure this, he allows himself initially to choose any subsequence and reverse its elements.

For example, if we had the list

1 6 2 3 4 3 5 3 4
We can reverse the chosen elements

1 6 2 3 4 3 5 3 4
  ^         ^ ^ ^
to get

1 4 2 3 4 3 3 5 6
  ^         ^ ^ ^

Observe how the subsequence being reversed ends up using the same indices as it initially occupied, leaving the other elements unchanged.

Please find the maximum possible length of an increasing subsequence, given that you can choose to reverse an arbitrary subsequence once.

FJ正在安排他的N头奶牛排成一队以拍照（1<=n<=50)。队列中的第i头奶牛的身高为a[i]，并且FJ认为如果奶牛的身高序列中含有一个很长的不下降子序列的话，这会是一张很好的照片。

回忆一下，子序列是由牛序列中的一些元素a[i_1],a[i_2],.....a[i_k]组成的子集。(i_1<i_2<...<i_k) 如果a[i_1]<=a[i_2]<=a[i_3]<=......<=a[i_k]的话，我们就说这个序列是不下降的。

FJ想要在他的奶牛序列中包括一个长期增长的子序列（也就是很长的不下降子序列）。为了确保这一点，他允许自己在一开始选择任何子序列并逆转其元素。

观察这个子序列（上方英文）是如何反转并占据他们最初的相同的位置的，且其他元素保持不变。

在只能反转一次任意子序列的情况下，请找到不下降子序列的最大可能长度。

输入格式

The first line of input contains $N$. The remaining $N$ lines contain $a(1) \ldots a(N)$, each an integer in the range $1 \ldots 50$.

第一行一个整数N。

接下来N行包括N个整数a[1]...a[n]，每行一个在1到50之间的整数。

输出格式

Output the number of elements that can possibly form a longest increasing subsequence after reversing the contents of at most one subsequence.

输出反转一次任意子序列后所得到的不下降子序列的最大可能长度。

9
1
2
3
9
5
6
8
7
4

9

提示

感谢 @XY星系质量PK 的翻译