#joi2021hoc. [joi2021ho_c]集合写真 (Group Photo)

[joi2021ho_c]集合写真 (Group Photo)

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

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

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

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

  • ii (1leqqileqqN1 \\leqq i \\leqq N) に立っている参加者の身長を aia_i とする. このとき,すべての ii (1leqqileqqN11 \\leqq i \\leqq N - 1) に対し,ai<ai+1+2a_{i} < a_{i + 1} + 2 が成り立つ.

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

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

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


入力

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

NN H1H_1 cdots\\cdots HNH_N

出力

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


制約

  • 3leqqNleqq5,0003 \\leqq N \\leqq 5\\,000
  • 1leqqHileqqN1 \\leqq H_i \\leqq N (1leqqileqqN1 \\leqq i \\leqq N).
  • HineqHjH_i \\neq H_j (1leqqi<jleqqN1 \\leqq i < j \\leqq N).

小課題

  1. (55 点) Nleqq9N \\leqq 9
  2. (77 点) Nleqq20N \\leqq 20
  3. (3232 点) Nleqq200N \\leqq 200
  4. (2020 点) Nleqq800N \\leqq 800
  5. (3636 点) 追加の制約はない.

入力例 1

5
3 5 2 4 1

出力例 1

以下のように操作を 33 回行うことで,条件を満たすようにできる.

  • まず,段 22 の参加者と段 33 の参加者を入れ替える.参加者の身長は前から順に 3,2,5,4,13, 2, 5, 4, 1 となる.
  • 次に,段 44 の参加者と段 55 の参加者を入れ替える.参加者の身長は前から順に 3,2,5,1,43, 2, 5, 1, 4 となる.
  • 最後に,段 33 の参加者と段 44 の参加者を入れ替える.参加者の身長は前から順に 3,2,1,5,43, 2, 1, 5, 4 となり,条件を満たす.

22 回以下の操作で条件を満たす状態にすることはできないので,33 を出力する.


入力例 2

5
3 2 1 5 4

出力例 2

すでに条件を満たしているので,操作を行う必要はない.


入力例 3

9
6 1 3 4 9 5 7 8 2

出力例 3