$FTY$有一个序列$a$，他定义一个序列的价值为其满足“优美”性质的子序列的最长长度。

一个序列$b$是优美的，当且仅当其满足$b_1<b_2 , b_2>b_3 , b_3<b_4, b_4>b_5 \dots$或$b_1>b_2 , b_2<b_3 , b_3>b_4, b_4<b_5 \dots$。

现在FTY想要知道序列$a$的价值是多少。

输入第一行一个整数$n(n \leq 2000)$，表示序列$a$的长度。

接下来一行共$n$个整数，其中第$i$个整数为$a_i(1\leq a_i \leq n)$。

输出一行一个整数表示序列$a$的价值。