問題文

とある合宿の最終日，合宿の参加者 $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$ 行で出力せよ．

5
3 5 2 4 1

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$ 点) 追加の制約はない．