順列 \(Q\) を挿入操作をし終えた数で区切ったときのその間にある挿入をまだしていない要素の個数の列 \(A=(A_0,A_1,...,A_k)\) として見ることを考えます。例えば、サンプル \(1\) だと \(A\) は \((3) \rightarrow (1,1) \rightarrow (0,1,0) \rightarrow (0,0,0,0)\) のようになります。さて、この時 \(i\) 回目の操作は以下のようになります。

• $A_k$ が正である最小の $k$ を取り、$A_k$ を $1$ 減らす。($i$ の削除操作)
• $A_x$ を $2$ 個の非負整数に分割する。ただし、$x=「P$ の要素のうち、$i$ 未満かつ $i$ より手前にあるものの個数」とする。($i$ の挿入操作)

さて、操作を逆から見ると以下のようになります。

• $A_x,A_{x+1}$ をマージする。($i$ の挿入操作)
• $A_0,A_1,\dots,A_{k-1}$ が全て $0$ であるような整数 $k$ を取り、$A_k$ を $1$ 増やす。($i$ の削除操作)

\(A=(0,0,\dots,0)\) から始めてこの操作を \(N\) 回繰り返して \(A=(N)\) にする方法の個数が求めるものです。

上記の操作において、「左から見て \(0\) が続いている個数」が一致している数列を同一視することが出来ます。よって、\(dp[i][j] = \)「逆から見たとき操作を \(i\) 回行い、\(A_0,A_1,\dots,A_{j-1} = 0\) であり、(存在するならば)\(A_{j} \neq 0\) であるような数列から \(A=(N)\) にする方法の個数」という動的計画法を行うことが出来ます。

初期状態は \(dp[0][N+1] = 1\) となります。遷移はまずマージにより \(j\) が \(1\) 減るか変わらないかを判定し、その後 \(k \le j\) を満たす \(k\) を選び遷移します。このままだと全体 \(\mathrm{O}(N^3)\) ですが、累積和を用いて \(\mathrm{O}(N^2)\) に高速化出来ます。

よって全体 \(\mathrm{O}(N^2)\) でこの問題が解けます。