关键观察

• 设连续三元组为 $(x,\,y,\,z)$。若删除中间元素 $y$，新的贡献变为 $|x-z|$。 要想权值不变，必须满足

  $$|x-y|+|y-z|=|x-z|.$$

• 上式等价于

题目内容

小A有一个长度为 $n$ 的数组 $a_1,a_2,...,a_n$ 。

定义数组的权值为 $|a_1-a_2,|+|a_2-a_3|...+|a_{n-1}-a_n|$，长度为 $1$ 的数组权值为 $0$ 。

现在小A想玩一个删数字的游戏，他想在数组中删去若干个数(不能全部删完)，并保证剩下数组的权值不变。

小A想知道在采取最优策略的情况下，他最多可以删掉多少个数字，你可以告诉他吗?

输入描述

第一行一个正整数 $n$ ，表示数字个数。

第二行 $n$ 个正整数，表示 $a_i$ 。

$1≤n≤10^5,1≤a_i≤10^9$

输出描述

输出一行，一个正整数，表示最多可以删去几个数。

样例1

输入

10
1 2 8 8 9 1 1 1 5 5

输出

6

样例2

输入

5
6 6 6 6 6

输出

4