Let us say an operation is essential when it is the last operation applied to that number.

The condition that the numbers of essential operations must satisfy

Consider the case we did \(L\) essential operations that moves a number to the beginning and \(R\) essential operations that moves a number to the end. Then, \(a_{L+1}, \dots, a_{n-R}\) were never subject of an operation, so their relative order did not change from the initial state \((1,2,\dots,n)\). Thus, this sequence must be monotonically increasing.

An \(O(n^2m)\) solution

The number chosen in the \(i\)-th last essential operation that moves a number to the beginning will be the \(i\)-th term in the final sequence, so this operation must choose \(a_i\). Similarly, the \(i\)-th last essential operation that moves a number to the end must choose \(a_{n-i+1}\). A non-essential operation may choose any number that will be chosen by a later operation and move it to either the beginning or the end.

From these, for \(L + R \le n\) such that \(a_{L+1}, \dots, a_{n-R}\) is monotonically increasing, there will be a unique sequence of operations if the following is decided:

• which \(L\) essential operations moves a number to the beginning;
• which \(R\) essential operations moves a number to the end;
• for each non-essential operation:
  • whether it moves a number to the beginning or the end;
  • which essential operation will move the number moved by that operation.

Thus, we can find the number of sequences of operations of length \(i\) containing \(l\) essential operation to the beginning and \(r\) essential operation to the end, dp[i][l][r], with the following dynamic programming: (the recurrence formula corresponds to constructing the sequence of operations backward.)

for i=0..m, l=0..n, r=0..n
    dp[i+1][l][r] += dp[i][l][r] * 2 * (l + r)  
    dp[i+1][l+1][r] += dp[i][l][r]
    dp[i+1][l][r+1] += dp[i][l][r]

After computing dp[i][l][r], we can sum up \(dp[m][L][R]\) over all \(L+R\le n\) such that \(a_{L+1},\dots,a_{n-R}\) is monotonically increasing to find the answer, but this method will have the complexity of \(O(n^2m)\).

An \(O(n^2m)\) solution

Here, let \(j=l+r\) (that is, the number of integers that will be subject of some operation).

Let dp2[i][l][r] be the number of ways to decide the following for a sequence of operations of length \(i\) containing \(j\) essential operations:

• whether each operation is essential;
• for each non-essential operation, which essential operation will move the number moved by that operation.

Choosing which of the \(j\) essential operations move a number to the beginning will determine the sequence of operations, so we have dp[m][l][r] == dp2[m][l+r] * binom(l+r, l) (binom is the binomial coefficient).

We can compute dp2[i][j] as follows:

for i=0..m, j=0..n
    dp2[i+1][j] += dp2[i][j] * 2 * j
    dp2[i+1][j+1] += dp2[i][j]

Now we are able to solve the problem in \(O(nm)\) time, which is fast enough under the constraints.

Sample implementation in C++

Sample implementation in Python