题目描述

$\red{Farmer John }$将他的 $\red{NN }$头奶牛排成一排拍照$\red{（1≤}$$\red{N≤}$$\red{50)}$.

第 $\red{i }$头奶牛的高度是$\red{a(i)，}$$\red{Farmer John }$认为，如果奶牛阵容中的奶牛高度增加的子序列很大，这将是一张美观的照片。

回想一下，子序列是来自奶牛序列的元素的子集 $\red{a(i1),a(i2),...,a(ik)}$一系列索引 $\red{i1<i2<…}$$\red{<ik}$。

如果$\red{a(i1)≤}$$\red{a(i2)≤…}$$\red{≤}$$\red{a(ik)，}$我们说子序列增加。

$\red{FJ }$希望在他的奶牛订单中有一个长期递增的子序列。

为了确保这一点，他允许自己最初选择任何子序列并反转其元素。

例如，如果我们有列表

1 6 2 3 4 3 5 3 4

我们可以反转选择的元素

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

要得到

1 4 2 3 4 3 3 5 6

观察被反转的子序列如何最终使用与它最初占用的索引相同的索引，而其他元素保持不变。

假设您可以选择将任意子序列反转一次，请找出递增子序列的最大可能长度。

输入格式

第一行输入包含$\red{N}$。

其余的$\red{N}$行包含一个$\red{（1）….}$$\red{a（}$$\red{N）}$，每个都是$\red{1…}$$\red{50}$的整数。

输出格式

输出在反转最多一个子序列的内容后可能形成最长递增子序列的元素数。

样例

输入样例

9
1
2
3
9
5
6
8
7
4

输出样例

9