C - 積み木
解説
/
実行時間制限: 2 sec / メモリ制限: 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