/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
問題文
以下の条件のいずれかを満たす長さ 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 の部分列のうちジグザグ列であるものの長さの最大値を求めてください。
部分列とは
数列の部分列とは、数列から 0 個以上の要素を取り除いた後、残りの要素を元の順序で連結して得られる数列のことをいいます。 例えば、(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
B の部分列 (5,2,4,3) はジグザグ列であり、長さは 4 です。
入力例 2
5 1 2 3 4 5
出力例 2
2
Problem Statement
A length-k sequence A=(A_1,\ldots,A_k) is a zigzag sequence if:
-
A_1 < A_2> A_3 < A_4 > \ldots , or
-
A_1 > A_2 < A_3 > A_4 <\ldots .
More formally, a sequence is said to be a zigzag sequence if and only if:
- A_i \neq A_{i+1}\ (1\leq i \leq k-1), and
- (A_{i+1}-A_i)(A_i-A_{i-1}) < 0\ (2\leq i \leq k-1).
Especially, note that a sequence of length one is always a zigzag sequence.
Given a length-N sequence B=(B_1,\ldots,B_N), find the maximum length of a subsequence of B that is a zigzag sequence.
What is a subsequence?
A subsequence of a sequence is obtained by removing zero or more elements from the original sequence and concatenating the rest preserving the order. For example, (10,30) is a subsequence of (10,20,30), but (20,10) is not a subsequence of (10,20,30).Constraints
- 1\leq N \leq 2 \times 10^5
- 1\leq B_i\leq 10^9
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N B_1 \ldots B_N
Output
Print the answer in one line.
Sample Input 1
7 5 1 2 3 4 3 3
Sample Output 1
4
The subsequence (5,2,4,3) of B is a zigzag sequence of length 4.
Sample Input 2
5 1 2 3 4 5
Sample Output 2
2