E: 凸凹数列

問題

長さ $N$ の数列 $A$ が与えられる。$A$ の $i$ 項目 は $A_i$ である。 あなたは、この数列に対して以下の操作を行うことができる。

$A$ を凸凹数列にするために必要な操作の最小回数を求めよ。

以下の条件を満たす長さ $N$ の数列を凸凹数列と定義する。

制約

入力形式

入力は以下の形式で与えられる。

$N$
$A_1 \dots A_N$

出力

凸凹数列にするために必要な操作の最小回数を出力せよ。また、末尾に改行も出力せよ。

サンプル

サンプル入力 1

5
1 2 3 4 5

サンプル出力 1

2

$2$ と $3$ 、 $4$ と $5$ に操作を行えば、 $1\ 3\ 2\ 5\ 4$ という凸凹数列になる。

サンプル入力 2

3
1 2 3

サンプル出力 2

1

$1$ と $2$ に操作を行う、あるいは $2$ と $3$ に操作を行うことで、凸凹数列になる。

サンプル入力 3

12
5 9 1 38 100 -23 4 16 -2 -10 -17 8

サンプル出力 3

2