What will Maroon do after the division? Since \(P\) is a permutation of \(1, \cdots, N\), he will simply sort the blocks in descending order of the value of the frontmost element before concatenating them.

Based on this, let us think of the optimal division. Obviously, \(Q\) will never be lexicographically smaller than \(P\). Thus, \(Q\) will equal \(P\), or equal \(P\) until at some element \(Q > P\). In the latter case, having a longer common part results in being lexicographically smaller.

Here, for simplicity, let us consider the following two cases:

When \(P_1 \leq K\)

We can minimize the frontmost element of \(Q\) by dividing \(P\) so that the blocks begin with \(1, 2, \cdots, K\), in which case \(Q\) will begin with \(K\). We have no other choice.

When \(P_1 > K\)

For example, if we divide \(P\) so that the blocks begin with \(P_1, 1, 2, \cdots, K-1\), we can keep \(P_1\) at the beginning. How long can the common part of \(P\) and \(Q\) become?

Consider the situation where we can make the first \(x\) blocks in \(Q\) match \(P\), and each block begins at indices \(i_1 (= 1), i_2, \cdots i_x\). Here, \(P_{i_1} > P_{i_2} > \cdots, P_{i_x}\) holds. If up to the right end of this rightmost block are fixed, we should have as many blocks to the left of it for a fixed \(i_x\). This is because the more blocks the remaining part has, the greater the frontmost element of the remaining part will be.

Based on this observation, we precompute the array \(dp\), where \(dp_i\) is the maximum possible \(k\) for \((1 =) j_1 < j_2 < \cdots, j_k (= i)\) such that \(P_{j_1} > P_{j_2} \cdots, P_{j_k}\). We can do it in \(\mathrm{O}(N \log N)\) time in a way similar to the way we find LIS, using segment tree, for example.

Now, in the previous situation, let us fix \(i := i_x\), the index where the rightmost block in the common part of \(P\) and \(Q\) begins, and consider the maximum possible length of this block. In the remaining part to the right of this block, we need to make \(K - dp_i\) blocks. Each of these blocks has to begin with an element smaller than \(P_i\), or it will affect the order of blocks and lead to a contradiction. Also, we want this block to be as long as possible, so let us extend this block until just before the \((K - dp_i)\)-th value from the right among the values smaller than \(P_i\). Then, in the right part, we will make each of the \(K - dp_i\) blocks begin with one of the smallest \(K - dp_i\) values.

Now, we want to compare the optimal divisions for individual choices of \(i\). Among those divisions for \(i\) that can handle the right part properly, we want to choose the one with the lexicographically greatest following value: (the length of the common part of \(P\) and \(Q\), the maximum number of blocks so far).

We can find the lengths of the common part by dealing with \(i\) in the order \(P_i = 1, 2, \cdots, N\), doing the following operations:

• get the \((K - dp_i)\)-th greatest value of a set
• add \(i\) to a set

We can do them in \(\mathrm{O}(N \log^2 N)\) time if we naively do binary searches using, for example, BIT, and in \(\mathrm{O}(N \log N)\) if we do binary searches on BIT or use Policy-Based Data Structures, for example, in C++.

Therefore, we can solve the problem in \(\mathrm{O}(N \log N)\) in total. (\(\mathrm{O}(N \log^2 N)\) should also be accepted.)