C - 集合写真 (Group Photo) Editorial /

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).

小課題

  1. (5 点) N \leqq 9
  2. (7 点) N \leqq 20
  3. (32 点) N \leqq 200
  4. (20 点) N \leqq 800
  5. (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

Source Name

JOI 2020/2021 本選 問題3