题目描述

定义一个波动序列$W_n$如下：

对于$\forall i \in [2, n - 1]$，要么$W_i < W_{i - 1}$且$W_i < W_{i + 1}$，要么$W_i > W_{i - 1}$且$W_i > W_{i + 1}$

现在对于一个给定序列$A$，要求求出最长波动子序列$W$的长度。

输入格式

第一行一个整数$n$，表示共有$n$个数

接下来一行是这$n$个数

输出格式

一个数，表示最长波动序列长度

输入输出样例 #1

输入 #1

5
1 3 2 4 5

输出 #1

4

说明/提示

一种可行的最长波动序列为1, 3, 2, 4

$n \leq 5e3$

$A_i \leq 100$