j01315. 最长摆动子序列 未做

给定整数序列 $a_1,\dots ,a_n$，删去其中一些元素（也可以不删），使剩下的序列严格摆动：相邻两数的大小关系严格交替（先升后降或先降后升均可）。求最长可能的剩余长度。

第一行一个正整数 $n$；第二行 $n$ 个整数 $a_i$。

一行一个整数，即最长摆动子序列长度。

• $1\le n\le 10^5$，$|a_i|\le 10^9$