题目描述

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

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

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

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

输入描述

第一行一个正整数 $n(1\le n\le 10^5)$ ，表示数字个数。

第二行 $n$ 个正整数，表示 $a_i(1\le a_i\le 10^9)$ 。

输出描述

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

样例1

输入

10
1 2 8 8 9 1 1 1 5 5

输出

6

样例2

输入

5
6 6 6 6 6

输出

4