Bookshelf

最小の操作回数で条件を満たせた場合の最終的な本の並び順を考えてみましょう。

操作を行うたびに本棚にある本の冊数は $1$ 冊少なくなります。

よって、最終的な本の並びは、$A$ の最長広義増加部分列であることが分かります。
つまり、最小の操作回数は最長広義増加部分列の長さを $N$ から引くことによって求めることができます。

最長広義増加部分列の長さは、動的計画法によって $O(N \log N)$ で求められるため、この問題を十分高速に解くことができました。