集合写真 (Group Photo)

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

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

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

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

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

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

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

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

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

\(N\)
\(H_1\) \(\cdots\) \(H_N\)

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

• \(3 \leqq N \leqq 5\,000\)．
• \(1 \leqq H_i \leqq N\) (\(1 \leqq i \leqq N\))．
• \(H_i \neq H_j\) (\(1 \leqq i < j \leqq N\))．

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

JOI 2021 · JCIOI · CC BY-SA 4.0