Farmer John 将 $N$ 头牛排成一队拍照（$1 \leq N \leq 50$）。第 $i$ 头牛的身高为 $a(i)$。他认为队列中按身高递增的子序列越长，照片越美观。

回顾定义：子序列由下标满足 $i_1 < i_2 < \ldots < i_k$ 的元素 $a(i_1), a(i_2), \ldots, a(i_k)$ 组成。若 $a(i_1) \leq a(i_2) \leq \ldots \leq a(i_k)$，就称其为递增子序列。

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

注意，被反转的子序列仍占据原来的下标，其他元素保持不变。

允许选择任意子序列反转一次，请求出递增子序列的最大可能长度。

输入格式

从标准输入读取。

第一行包含 $N$。其余 $N$ 行包含 $a(1) \ldots a(N)$，每个是 $1 \ldots 50$ 范围内的整数。

输出格式

输出到标准输出。

输出至多反转一个子序列后，最长递增子序列可能包含的元素数。

样例

输入格式 1

9
1
2
3
9
5
6
8
7
4

输出格式 1

9

题目作者：Lewin Gan