C - 積み木 Editorial /

Time Limit: 2 sec / Memory Limit: 256 MB

問題文

全て高さの違う N 個の積み木が 1 列に並べられています。隣り合う 2 個の積み木を並べ替える操作を何回か行って、一番高い積み木から順に左右へ低くなっていくようにする時、必要な最小の交換回数を求めてください。すなわち、並べ替えた後の i 番目の積み木の高さを Ai とし、一番高い積み木の位置を T としたとき、

  • A1 < A2 < ... < AT > ... > AN-1 > AN
を満たすように並べ替えるのに必要な最小の交換回数を求めてください。

入力

入力は以下の形式で標準入力から与えられる。

N
B1 B2 ... BN
  • 1 行目には、積み木の数 N (1≦N≦10^5) がスペース区切りで与えられる。
  • 2 行目には、積み木の高さ Bi (1≦Bi≦N) が最初に並べられている順に与えられる。
  • ただし、積み木の高さは全て異なる。すなわち、Bi≠Bj (i≠j) が成り立つ。

出力

並べ替えるのに必要な最小の交換回数を出力せよ。出力の末尾には改行をつけること。

部分点

この問題には 2 つのデータセットがあり、データセット毎に部分点が設定されている。

  • N≦100 を満たすデータセット 1 に正解した場合は 30 点が与えられる。
  • 追加制約のないデータセット 2 に正解した場合は、上記のデータセットとは別に 70 点が与えられる。

入力例1

4
2 4 1 3

出力例1

1

以下のように 1 回で並べ替えられます。

入力例2

5
2 4 1 3 5

出力例2

3

3 回で並べ替える一例を示します。

入力例3

6
1 2 4 3 5 6

出力例3

1