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 翻译