操作後の \(P\) としてあり得る数列の特徴付けをします．

各 \(i\) について，入力の \(P_i\) が最終的に占めている位置は区間をなします． この区間を \([l_i,r_i)\) で表すことにします．

区間が空のときは \(l_i,r_i\) が一意に定まりませんが，\(r_i=l_{i+1}\) を追加の制約として課すことで，一意になります．

各 \(i\) について，以下のように \(L_i,R_i\) を定義します．

• \(j<i,P_j>P_i\) を満たす \(j\) が存在するならば，その中で最大のものを \(L_i\) とする．存在しないならば \(L_i=0\) とする．
• \(j>i,P_j>P_i\) を満たす \(j\) が存在するならば，その中で最小のものを \(R_i\) とする．存在しないならば \(R_i=N+1\) とする．

\(l_i,r_i\) が満たすべき条件は，以下のようにまとめられます．

• \(1=l_1 \leq r_1 = l_2 \leq r_2 = \cdots =l_N \leq r_N=N+1\)
• \(L_i < l_i < r_i \leq R_i\) もしくは \(l_i=r_i\)

逆に，これらの条件を満たす \(l_i,r_i\) は実際に達成できます． （値の小さいものから順に，その値が占める範囲を \([l_i,r_i)\) を含むまで広げればよいです．）

上の条件を満たす \(l_i,r_i\) の個数は DP で計算できます． \(i\) の昇順に \(l_i,r_i\) を決定していって，\(dp[i][j]=(r_i=j\)となる場合の数\()\) とすればよいです．

この DP は \(O(N^2)\) で計算できます．

解答例(c++)

おまけ

\(O(N\log^2N)\) 時間でも解けます．

解答例(c++)