Time Limit: 4 sec / Memory Limit: 512 MB
配点: 100 点
とある合宿の最終日,合宿の参加者 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).
小課題
- (5 点) N \leqq 9.
- (7 点) N \leqq 20.
- (32 点) N \leqq 200.
- (20 点) N \leqq 800.
- (36 点) 追加の制約はない.
入力例 1
5 3 5 2 4 1
出力例 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 を出力する.
入力例 2
5 3 2 1 5 4
出力例 2
0
すでに条件を満たしているので,操作を行う必要はない.
入力例 3
9 6 1 3 4 9 5 7 8 2
出力例 3
9