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