该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

给定 $n$ 个整数组成的序列 $a_1,a_2,⋯ ,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,⋯ ,a_n$。

输出格式

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

样例

6
1 3 5 2 4 6

4

数据范围

• 对于$100\%$的数据：$1≤n≤10^4$，$1≤a_i≤10^5$