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