← 返回题目列表

AtCoder · past19_l

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 这是一个锯齿序列。

什么是子序列? 序列的 A 子序列 长度为 $$$m$$$ 的 是通过从原始序列中删除零个或多个元素并连接其余元素并保持顺序来获得的。 例如, (10,30) 是以下序列的子序列 (10,20,30),但是 (20,10) 不是以下序列的子序列 (10,20,30).

约束

  • 1\leq N \leq 2 \times 10^5
  • 1\leq B_i\leq 10^9
  • 所有输入值均为整数。

输入

输入由标准输入按以下格式给出:

N 
B_1 \ldots B_N

输出

在一行中打印答案。


示例输入 1

7
5 1 2 3 4 3 3

示例输出 1

4

子序列 (5,2,4,3) of B 是一个长度为锯齿形的序列 4.


示例输入 2

5
1 2 3 4 5

示例输出 2

2