AT_past19_l 最長のジグザグ

以下の条件のいずれかを満たす長さ $ k $ の数列 $ A=(A_1,\ldots,A_k) $ をジグザグ列と呼びます。 - $ A_1 < A_2> A_3 < A_4 > \ldots $ - $ A_1 > A_2 < A_3 > A_4

入力は以下の形式で標準入力から与えられる。 > $ N $ $ B_1 $ $ \ldots $ $ B_N $

答えを一行に出力せよ。

### Sample Explanation 1 $ B $ の部分列 $ (5,2,4,3) $ はジグザグ列であり、長さは $ 4 $ です。 ### Constraints - $ 1\leq N \leq 2 \times 10^5 $ - $ 1\leq B_i\leq 10^9 $ - 入力は全て整数