自由度が高いので、作ることの出来る数列はかなり多そうです。試しにすべての要素が同じ数列を作れるか考えると、\(A\) に含まれていない \(X\) 以下の正整数が存在するとき、またそのときのみ作れることがわかります。

よって、この問題は以下のような問題に帰着できます。

• \(A\) をいくつかの連続部分列に分解して、どの部分列にも、含まれていない \(X\) 以下の正整数が存在するようにしたい。最小でいくつに分解する必要があるか？

これは、先頭から伸ばせるだけ伸ばして、伸ばせないなら切ればよいです。数列は短いほうが少ない数に分解しやすいので、伸ばせるときに切るのは損だからです。この処理は \(O(N)\) の時間計算量で行えます。