問題文

とある合宿の最終日，合宿の参加者 $N$ 人で集合写真を撮ることとなった．参加者には身長の低い順に $1$ から $N$ までの番号が付けられている．参加者 $h$ の身長は $h$ である ($1 \leq h \leq N$)．

集合写真は，階段の上に並んで撮影する．この階段はちょうど $N$ 段からなり，低い方から順に $1$ から $N$ までの番号が付けられている．段 $i + 1$ は段 $i$ よりもちょうど $2$ だけ高い ($1 \leq i \leq N − 1$)．階段の幅はとても狭いため，それぞれの段に参加者が $1$ 人ずつ立って，縦一列に並んで撮影する．

間もなく撮影が行われようとしており，それぞれの段に参加者が立っている．現在，段 $i$ ($1 \leq i \leq N$) に立っている参加者は，参加者 $H_i$ である．

ところが，あまりにも参加者の身長が違いすぎるため，この並び順では写真に写らない参加者がいるかもしれない．そこで，あなたは参加者の位置を並べ替えて，少なくとも全員の頭の上部が写るようにしたい．すなわち，次の条件が満たされるようにしたい．

• 段 $i$ ($1 \leq i \leq N$) に立っている参加者の身長を $a_i$ とする．このとき，すべての $i$ ($1 \leq i \leq N − 1$) に対し，$a_i < a_{i+1} + 2$ が成り立つ．

ただし，あなたは隣り合う参加者の位置を入れ替えることしかできない．すなわち，$1$ 回の操作において， 段 $i$ ($1 \leq i \leq N − 1$) を任意に一つ選び，段 $i$ の参加者と段 $i + 1$ の参加者を入れ替えることができる．

この操作をできるだけ少ない回数行うことで，条件が満たされるようにしたい．

現在の参加者の並び順が与えられたとき，必要な操作回数の最小値を求めるプログラムを作成せよ．

入力

入力は以下の形式で標準入力から与えられる．入力される値はすべて整数である．

$N$
$H_1 \ldots H_N$

出力

必要な操作回数の最小値を，標準出力に $1$ 行で出力せよ．

入出力例 1

5
3 5 2 4 1

3

以下のように操作を $3$ 回行うことで，条件を満たすようにできる．

• まず，段 $2$ の参加者と段 $3$ の参加者を入れ替える．参加者の身長は前から順に $3, 2, 5, 4, 1$ となる．
• 次に，段 $4$ の参加者と段 $5$ の参加者を入れ替える．参加者の身長は前から順に $3, 2, 5, 1, 4$ となる．
• 最後に，段 $3$ の参加者と段 $4$ の参加者を入れ替える．参加者の身長は前から順に $3, 2, 1, 5, 4$ となり，条件を満たす．

$2$ 回以下の操作で条件を満たす状態にすることはできないので，$3$ を出力する．

5
3 2 1 5 4

0

すでに条件を満たしているので，操作を行う必要はない．

9
6 1 3 4 9 5 7 8 2

9

制約

• $3 \leq N \leq 5000$．
• $1 \leq H_i \leq N$ ($1 \leq i \leq N$)．
• $H_i \neq H_j$ ($1 \leq i < j \leq N$)．

小課題

1. ($5$ 点) $N \leq 9$．
2. ($7$ 点) $N \leq 20$．
3. ($32$ 点) $N \leq 200$．
4. ($20$ 点) $N \leq 800$．
5. ($36$ 点) 追加の制約はない．