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)$ なら増加部分列と呼びます。

長い増加部分列を得るため、初めに任意の部分列を選んでその要素を逆順にしてよいとします。

例えば次の列で、

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

反転した部分列は元と同じ添字を使い、他の要素は変わらない点に注意してください。

任意の部分列を 1 回反転できるとき、増加部分列の最大長を求めてください。

入力

標準入力から読みます。

最初の行は $N$ です。続く $N$ 行は $a(1) \ldots a(N)$ で、各値は $1 \ldots 50$ の整数です。

出力

標準出力に書きます。

高々 1 つの部分列を反転した後に得られる最長増加部分列の要素数を出力してください。

入出力例

入力 1

9
1
2
3
9
5
6
8
7
4

出力 1

9

問題作成者：Lewin Gan