とある合宿の最終日，合宿の参加者 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 の参加者を入れ替えることができる．

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

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

制約

• 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