集合写真(Group Photo)

とある合宿の最終日,合宿の参加者N 人で集合写真を撮ることとなった.参加者には身長の低い順に1
からN までの番号が付けられている.参加者h の身長はh である(1 ≦h ≦N).
集合写真は,階段の上に並んで撮影する.この階段はちょうどN 段からなり,低い方から順に1 からN
までの番号が付けられている.段i + 1 は段i よりもちょうど2 だけ高い(1 ≦i ≦N −1).階段の幅はとて
も狭いため,それぞれの段に参加者が1 人ずつ立って,縦一列に並んで撮影する.
間もなく撮影が行われようとしており,それぞれの段に参加者が立っている.現在,段i (1 ≦i ≦N) に
立っている参加者は,参加者Hi である.
ところが,あまりにも参加者の身長が違いすぎるため,この並び順では写真に写らない参加者がいるかも
しれない.そこで,あなたは参加者の位置を並べ替えて,少なくとも全員の頭の上部が写るようにしたい.
すなわち,次の条件が満たされるようにしたい.
• 段i (1 ≦i ≦N) に立っている参加者の身長をai とする.このとき,すべてのi (1 ≦i ≦N −1) に対
し,ai < ai+1 + 2 が成り立つ.
ただし,あなたは隣り合う参加者の位置を入れ替えることしかできない.すなわち,1 回の操作において,
段i (1 ≦i ≦N −1) を任意に一つ選び,段i の参加者と段i + 1 の参加者を入れ替えることができる.
この操作をできるだけ少ない回数行うことで,条件が満たされるようにしたい.
現在の参加者の並び順が与えられたとき,必要な操作回数の最小値を求めるプログラムを作成せよ.

• 3 ≦N ≦5 000.
• 1 ≦Hi ≦N (1 ≦i ≦N).
• Hi , Hj (1 ≦i < j ≦N).

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

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

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

第20 回日本情報オリンピック(JOI 2020/2021) 本選
2021 年2 月14 日(オンライン開催)

생성자가 기록되지 않았습니다.

출처 JOI 2021 Final