题目描述

所谓摆动序列，即数字之间的差在正数和负数之间不断交替。仅包含一个元素的序列或者包含两个不相等元素的序列也视作摆动序列。

例如：

• $[1, 7, 4, 9, 2, 5]$是一个摆动序列，因为相邻数的差值$(6,-3,5,-7,3)$是正负交替的。
• 而$[1, 4, 7, 2, 5]$ 与 $[1, 7, 4, 5, 5]$不是摆动序列。

现给出一个长度为 $n$ 的整数数组 $nums$，你可以删除其中的任意个元素，使得整个数组成为一个摆动序列。

请求出如此得到的摆动序列最长能有多长。

格式

输入

第一行，为一个整数 $n$。 第二行，为 $n$ 个整数 $a_i$。

输出

一个整数，即最终得到的摆动序列的最长长度。

样例

6
1 7 4 9 2 5

6

10
1 17 5 10 13 15 10 5 16 8

7

提示

样例说明2

可以删除元素 $10,13,10$，得到新的序列 $[1, 17, 5, 15, 5, 16, 8]$ ，各元素之间的差值为 $(16, -12, 10, -10, 11, -8)$ 。

数据范围

$1 \leq n \leq 1000$ $0 \leq a_i \leq 1000$