题目描述

数学中，一个序列如果连续项之间的差值严格地在正数和负数之间交替，则称为 "摆动序列"。第一个差值（如果存在的话）可以是正数或负数。仅有一个元素或者包含两个不等元素的序列也被认为是摆动序列。

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

相反， $[3, 8, 11, 4, 6]$ 和 $[3, 9, 6, 7, 7]$ 都不是符合要求的序列，第一个序列是因为它的前两个差值都是正数，第二个序列是因为它的最后一个差值为零。

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

现在给定一个长度为 $n$ 的序列 a，返回 a 中作为摆动序列的最长子序列的长度。

输入格式

第一行包含一个整数 $n$

第二行包含 $n$ 个整数 $a_i$

$1≤n≤5000 , 0≤a_i≤5*10^4$

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

5
1 2 100 123 99