题目描述
给定 $n$ 个整数组成的序列 $a_1,a_2,\cdots,a_n$，请从中挑出尽量长的子序列，形成一个锯齿序列。所谓锯齿序列，就是它的差分序列（由相邻数字的差组成的序列）是正负交替的。为了避免差为 $0$ 时不方便区分正负，保证给定的每个数字都不相同。
例如给定的序列是 $1,3,5,2,4,6$，那么它的子序列 $1,5,2,6$ 是一个锯齿序列，因为它的差分序列是 $4,-3,4$；而 $1,3,5$ 不是，因为这三个数字是递增的。
输入
第一行：一个整数 $n$
第二行：$n$ 个整数 $a_1,a_2,\cdots,a_n$
输出
单个整数：表示最长的锯齿子序列长度
样例输入输出
提示
对于$30\%$的数据：$1\leq n\leq 10$
对于$60\%$的数据：$1\leq n\leq 10^3$
对于$100\%$的数据：$1\leq n\leq 10^4$，$1\leq a_i\leq 10^5$