ARC031 C - 積み木

問題：C - 積み木

解答：Submission #13584602 - AtCoder Regular Contest 031

解法：まず1の移動先を考えると、これは1番左か1番右になる。仮に近い方に置くとする。
次に2の移動先を考える。これは1を除いて1番左か1番右となる。つまり、先に置いた1の位置に関係なく決まる。

上記の考察より、小さい順に1番左か1番右の近い方に置き、その数を除いてゆくことで答えを求めることができる。
これは初期値1のBinaryIndexedTreeを用い、ある項xを除くことをadd(x, -1)と見なすことで求められる。