题目描述

如果连续数字之间的差严格地在正数和负数之间交替，则数字序列称为摆动序列。第一个差（如果存在）可以是正数或负数。仅有一个元素或者含两个不等元素的序列也视作摆动序列。

例如，$[1, 7, 4, 9, 2, 5]$ 是一个摆动序列，因为差值 $(6, -3, 5, -7, 3)$ 是正负交替出现的。

相反，$[1, 4, 7, 2, 5]$ 和 $[1, 7, 4, 5, 5]$ 不是摆动序列。第一个序列是因为它的前两个差值都是正数，第二个序列是因为它的最后一个差值为零。

子序列可以通过从原始序列中删除一些元素（也可以不删除）来获得，剩下的元素保持其原始顺序。

给定一个长度为 $n$ 的整数数组 $nums$，输出 $nums$ 中作为摆动序列的最长子序列的长度。

输入格式

第一行输入一个整数 $n$。

第二行输入 $n$ 个整数 $nums_i$。

输出格式

输出一个整数，表示摆动序列的最长子序列长度。

样例

6
1 7 4 9 2 5

6

数据范围

$1 \le n \le 1000$。

$0 \le nums_i \le 1000$。