문제

とある合宿の最終日，合宿の参加者 $N$ 人で集合写真を撮ることとなった．参加者には身長の低い順に $1$ から $N$ までの番号が付けられている．参加者 $h$ の身長は $h$ である（$1 \le h \le N$）．

集合写真は，階段の上に並んで撮影する．この階段はちょうど $N$ 段からなり，低い方から順に $1$ から $N$ までの番号が付けられている．段 $i+1$ は段 $i$ よりもちょうど $2$ だけ高い（$1 \le i \le N-1$）．階段の幅はとても狭いため，それぞれの段に参加者が $1$ 人ずつ立って，縦一列に並んで撮影する．

間もなく撮影が行われようとしており，それぞれの段に参加者が立っている．現在，段 $i$（$1 \le i \le N$）に立っている参加者は，参加者 $H_i$ である．

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

• 段 $i$（$1 \le i \le N$）に立っている参加者の身長を $a_i$ とする．このとき，すべての $i$（$1 \le i \le N-1$）に対し，$a_i < a_{i+1} + 2$ が成り立つ．

ただし，あなたは隣り合う参加者の位置を入れ替えることしかできない．すなわち，$1$ 回の操作において，段 $i$（$1 \le i \le N-1$）を任意に一つ選び，段 $i$ の参加者と段 $i+1$ の参加者を入れ替えることができる．

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

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

입력

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

N
H_1 \ldots H_N

출력

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

예제 입력 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

제한

• $3 \le N \le 5\,000$．
• $1 \le H_i \le N$（$1 \le i \le N$）．
• $H_i \ne H_j$（$1 \le i < j \le N$）．

서브태스크

1. ($5$ 점) $N \le 9$．
2. ($7$ 점) $N \le 20$．
3. ($32$ 점) $N \le 200$．
4. ($20$ 점) $N \le 800$．
5. ($36$ 점) 追加の制約はない．