分割を決めた後の maroon 君の挙動を考えてみましょう．これは \(P\) が順列であることから単純にブロックの先頭の値でソートして大きい方から繋げていけばよいです．

これを踏まえて最適な分割について考えてみます．明らかに，\(Q\) が \(P\) より辞書順で小さくなることはありません．よって，\(Q\) は \(P\) と等しいか，\(P\) と途中まで等しく，ある項で \(Q > P\) となっています．後者であれば共通する長さが異なるものの中では共通部分が長い方が辞書順で小さくなります．

ここで，簡単のため \(P_1\) と \(K\) の大小関係で場合分けします．

\(P_1 \leq K\) のとき

\(Q\) の先頭を最小化することを考えると，各ブロックの先頭が \(1, 2, \cdots, K\) となるように分割することで先頭を \(K\) にすることができ，またこれ以外の方法はありません．

\(P_1 > K\) のとき

この場合は例えばブロックの先頭の値が \(P_1, 1, 2, \cdots, K-1\) となるように選ぶと先頭を \(P_1\) のままにできます．ではどこまで \(P\) との共通部分を長くすることができるでしょうか．

\(x\) 個のブロックまで \(P\) と等しくでき，各ブロックの先頭の index が \(i_1 (= 1), i_2, \cdots i_x\) であるような状況を考えます．このとき \(P_{i_1} > P_{i_2} > \cdots, P_{i_x}\) が成り立っています．この右端のブロックの終端まで決まっている状況を考えると，\(i_x\) を固定したときはその左側でできるだけ多くのブロックに分割されている方が得です．なぜなら残りの部分で分ける個数が増えるほど，\(Q\) の中での残りの部分の先頭が大きくなるからです．

このため，前もって \(dp_i := P_{j_1} > P_{j_2} \cdots, P_{j_k}\) となるような \((1 =) j_1 < j_2 < \cdots, j_k (= i)\) に対する \(k\) の最大値，として \(dp\) 配列を計算しておきます．これは LIS を求める DP と同様に segment tree などを使って \(\mathrm{O}(N \log N)\) で可能です．

先程の状況で \(P\) と共通となる一番右のブロックの先頭 \(i := i_x\) を固定して，\(i\) から始まるブロックをどこまで伸ばすことができるかを考えます．このブロックより右の残りの部分で，ブロックを \(K - dp_i\) 個作る必要があります．残りのブロックの先頭が全て \(P_i\) より小さくないと，どこかでブロックの順番が変わってしまい矛盾します．また，このブロックはできるだけ伸ばす方が良いので，\(P_i\) より小さい値の中で index が大きい方から \(K - dp_i\) 個目のものの手前まで伸ばします．すると残りの部分は小さい方から \(K - dp_i\) 個をそれぞれブロックの先頭として分割することになります．

あとは \(i\) ごとの最適な分割同士の比較できればよいですが，残りを適切に分けることのできるような \(i\) に対する分割の中では，(\(P\) との共通な部分の長さ，そこまでのブロックの最大個数) の辞書順で一番大きいものが良いです．

共通部分の長さを求めるパートは，\(P_i = 1, 2, \cdots ,N\) となる \(i\) の順に \(i\) を見ていき，

• 集合の大きい方から \(K - dp_i\) 番目の値を取得する
• 集合に \(i\) を追加する

という操作を行うことで可能ですが，この操作は BIT などを用いて単純に二分探索すると \(\mathrm{O}(N \log^2 N)\), BIT 上で二分探索するか，C++ なら Policy-Based Data Structures などを用いると \(\mathrm{O}(N \log N)\)で可能です．

よって全体の計算量は \(\mathrm{O}(N \log N)\) です．( \(\mathrm{O}(N \log^2 N)\) でも AC できるはずです)