301012 - 最长波浪子序列

如果一个序列满足 a1 < a2 > a3 < a4 > ... 或 a1 > a2 < a3 > a4 < ...，称为波浪序列。求最长波浪子序列的长度。

第一行为一个整数 n（n ≤ 15000）。 第二行为 n 个数，每个数不超过 int 范围。

输出一个数，即最长波浪子序列的长度。