题目描述

给你一个长度为 $n$ 的序列 $a_1\sim a_n$，请你求出该子序列的最长波动子序列长度。
波动子序列：称 $b$ 为 $a$ 的波动子序列当且仅当 $b$ 是 $a$ 的子序列，且 $b$ 相邻两个元素不相同，且 $b$ 不会出现两个连续增长或者连续下降的元素。

输入格式

第一行一个整数 $n(1\le n\le 5000)$。
第二行 $n$ 个整数 $a_1\sim a_n(1\le a_i\le 10^9)$。

输出格式

一行一个整数，表示答案。

输入输出样例 #1

输入 #1

6
1 1 2 2 1 1

输出 #1

3