AT_past19_l 最長のジグザグ

长度为 $k$ 的序列 $A=(A_1,\ldots,A_k)$ 被称为锯齿序列，当且仅当： - $A_1 < A_2 > A_3 < A_4 > \ldots$ ，或者 - $A_1 > A_2 < A_3 > A_4 < \ldots$。 更形式化地说，若且仅若序列满足以下条件时，被称为锯齿序列： - $A_i \neq A_{i+1}\ (1 \leq i \leq k-1)$，并且 - $(A_{i+1} - A_i)(A_i - A_{i-1}) < 0\ (2 \leq i \leq k-1)$。 特别地，长度为 $1$ 的序列始终为锯齿序列。 给定一个长度为 $N$ 的序列 $B=(B_1,\ldots,B_N)$，请你求出 $B$ 的最长锯齿子序列的长度。 什么是子序列？**子序列**是指从原序列中删除零个或多个元素，余下元素按原顺序依次排列所得到的序列。例如，$(10,30)$ 是 $(10,20,30)$ 的子序列，但 $(20,10)$ 不是 $(10,20,30)$ 的子序列。

输入从标准输入读入，格式如下： > $N\ B_1\ \ldots\ B_N$

一行输出一个整数，表示最长锯齿子序列的长度。

### 样例解释 1 序列 $B$ 的子序列 $(5,2,4,3)$ 是一个长度为 $4$ 的锯齿序列。 ### 数据范围 - $1 \leq N \leq 2 \times 10^5$ - $1 \leq B_i \leq 10^9$ - 所有输入值均为整数。 由 ChatGPT 5 翻译