No.031 C 問題 コード 1から順番に端に移動させていく. このとき, 左右で距離の短い方に寄せる. ここで, 数 の左端(右端)までの距離は, より左側(右側)にある より大きい数の個数である. これは より小さい数はすでに端に寄せられているため無関係となるからである. これをあらかじめ数えておけば, どちらに寄せればいいかはすぐにわかる. これは転倒数と似ているので, 計算も同様に Binary Indexed Tree を使うのが速い.