题目描述

给定 $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$

输出格式

单个整数：表示最长的锯齿子序列长度

6
1 3 5 2 4 6

4

数据范围

对于$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$