ABC006 D - トランプ挿入ソート

https://atcoder.jp/contests/abc006/submissions/15555175

• ソートするためには最低でも最長増加部分列（LIS）以外は移動する必要がある

マージソートなどは木構造を使って1枚あたりの計算量をに減らすが、これは計算量を求める問題ではない。どんなソートを使っても最長増加部分列以外のカードを動かさないと永遠にソートされないため N - Size(LIS) が答えになる。