Consider the permutation \(Q\) such that \(P_{Q_i}=i\).

Looking at the operations in reverse, for the permutation \((1,2,3,\dots,N)\), the problem is to find the minimum cost to convert the permutation to \(Q\) by performing this operation: take some terms to the end while maintaining their order.

The operation “take some terms to the end while maintaining their order” behaves the same as radix sort with base \(B=2\). Let’s explain this a little more rigorously. Prepare a non-negative integer sequence \(X=(X_1,X_2,\dots,X_N)\). Initially, \(X_i=0\ (1\leq i \leq N)\). When the integer \(i\) is taken to the end in the \(k\)-th operation, replace \(X_i\) with \(X_i+2^k\). After \(K\) operations, the permutation obtained in the end is one where \(i\ (1\leq i \leq N)\) is stably sorted in ascending order of \(X_i\). Then, to obtain permutation \(Q\), it is necessary and sufficient to perform a series of operations such that \(X_i \leq X_{i+1}\) if \(Q_i < Q_{i+1}\), and \(X_i < X_{i+1}\) if \(Q_{i} > Q_{i+1}\).

Therefore, the problem can be rephrased as follows.

For a non-negative integer \(n\) less than \(2^K\), let \(n\) be represented in binary as \(n=\sum_{i=1}^{m}2^{k_i}\), and let \(f(n)=\sum_{i=1}^{m}C_{K-k_i}\).

Find the minimum value of \(\sum_{i=1}^{N}f(X_i)\) for a non-decreasing sequence \(X\) of length \(N\) with non-negative integers that satisfy the following conditions:

• \(X_i < X_{i+1}\) if \(Q_{i} > Q_{i+1}\);
• \(X_N < 2^K\).

This can be solved by interval DP fixing the smallest \(i\) such that \(2^{k} \leq X_i\), in \(O(KN^3)\) time.

(Modified the first draft written by GPT-4.)