题目描述

小明在坐过山车。

假设​** 是小明坐过山车时的初始位置点高度，对于任意的 ​，我们可以求出任意两个相邻位置的高度差为 ​。小明认为，一个足够刺激好玩的过山车必须满足：相邻高度差的正负号是交替的，也就是过山车必须满足如下图的升降曲线。**

我们可以将一些位置点删除，使得该过山车是小明认定的足够刺激好玩的过山车，要尽量使删除的位置点最少，求最终剩余位置点的个数。

输入格式

两行。

第一行一个正整数 ​ ，表示过山车的初始位置点个数。

第二行 ​ 个非负数 ​ ，表示初始位置高度。

输出格式

一行，一个正整数，表示最终结果。

样例 #1

样例输入 #1

6
 1 3 2 6 4 5

样例输出 #1

6

提示

【数据范围】

$1\le n \le 10^6,1\le a_i \le 10^6$。