\(P\) のLIS長を \(L\) とします． また，求める答えを \(ans=(ans_1,\cdots,ans_N)\) とおきます．

各要素 \(P_i\) について，それからスタートする単調増加部分列の長さの最大値を \(v_i\) とします．

swap 操作ごとに \(v_i\) も更新されるものとします． まず，各 \(P_i\) について，それに対応した \(v_i\) が減ることはありません．(\(i\) から \(v_i\) への対応ではなく \(P_i\) から \(v_i\) への対応を考えていることに注意)

\(v_i=L\) となる添え字 \(i\) を \(i_1<i_2<\cdots<i_k\) とします． 各 \(i_j\) について，それより左にそれより小さい値が来ることはありません．さもなくば，\(P\) の LIS 長が \(L\) を超えるからです．

すると，\(ans\) の先頭 \(k\) 要素は \(P_{i_1},\cdots,P_{i_k}\) になるとわかります． なお，このような順列に到達するような操作列が必ず存在します． 素直に \(1\) 要素ずつ先頭に持ってくるだけでよいです．

\(P_{i_k}>1\) の場合，\(ans_{k+1}=1\) にできます． これは \(1\) を前に持ってくれば達成できます．

今，\(v_i=L\) となる要素と \(P_i\) が最小 (今の場合は \(1\)) になる要素を処理しましたが，全く同じ要領で \(v_i=L-1,L-2,\cdots\) を処理することができます． \(v_i\) の値は最初に全部求めてしまえばその後更新する必要がないです．

よって以上の操作をそのまま実装すれば，全体の計算量 \(O(N \log N)\) の解法が得られます．

writer解(C++)