题目描述

不想形成浪花的大海不是好大海。

昨天，机电学院的叶墨凌同学来到了未来圣城Karolance南部的海洋。这是一片完全由数字构成的海洋，海平面上奔腾着汹涌的数字浪花。他发现，每一个数字都代表着一个海浪的高度。可是，这样凌乱的浪花实在是有违大海的美感，于是他想搬走几朵浪花来修整一下浪花的形态，你可以帮帮他么？

给定一个浪花序列a，从中选出若干元素，顺序同原序列，构成一个子序列b，b满足对于所有的 i ：

$$b_{2i} > b_{2i-1} $$ $$ b_{2i} > b_{2i+1} $$

或者

$$b_{2i} < b_{2i-1} $$ $$ b_{2i} < b_{2i+1} $$

特别地，当b的长度为1时，两个条件视为全部满足；当b的长度不为1时，只能满足其中一个条件

求b的最大长度

输入格式

序列a的长度n

n个用空格隔开的整数

输出格式

一个整数，表示b的最大长度

7
2 3 2 1 2 3 2

5

提示

$1\leqslant n\leqslant 1000000$

$1\leqslant a_i\leqslant 2147483647$