E: 凸凹数列

問題

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

• $1 \leq i \leq N - 1$ なる整数 i を選ぶ。 $A_i$ の値と $A_{i + 1}$ の値を入れ替える。

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

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

• $1 < i < N$ を満たす任意の $i$ について、 $A_{i + 1}, A_{i - 1} > A_i$ または $A_{i + 1}, A_{i - 1} < A_i$ を満たす。
  直感的に言えば、 $1,\ 10,\ 2,\ 30,\ \dots (10,\ 1,\ 30,\ 2,\ \dots )$ のような、増加、減少、増加…（減少、増加、減少…）を繰り返す数列である。

制約

• 入力値は全て整数である。
• $3 \leq N \leq 10^5$
• $i \neq j$ ならば $A_i \neq A_j$
• $-10^9 \leq A_i \leq 10^9$

入力形式

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

$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

Note

Commentary

 

---