\(1 \le a \le N\) に対して、\(X_i = a\) となる \(i\) のうち小さいほうを \(L_a\)、大きいほうを \(R_a\) とする。

公式解説同様に、\(L_a < L_b\) かつ \(R_a < R_b\) のときに限り、最終的な数列において \(a\) が \(b\) より前の項で現れることが確定する。

つまり、このような条件を満たすような \((a, b)\) の組に対し、\(a\) から \(b\) に辺を張ったグラフにおいて、辞書順最小のトポロジカルソート順を求めればよいことがわかる。

実際に辺をすべて張ると最大で \(O(N^2)\) 本になってしまうので、分割統治によって辺の本数を減らすことを考える。

\(l < L_a < r\) を満たすような \(a\) についての処理を考える。 \(m = (l + r) / 2\) として、\(L_a < m \le L_b\) を満たすような \((a, b)\) についての辺を張り、それ以外については \((l, m), (m, r)\) において再帰的に同様の処理を行うことにする。

\(L_a < m \le L_b\) を満たすような \((a, b)\) については、左右それぞれ \(R_a\) の昇順に仮想的な頂点を並べ、\(R_a\) の大小関係に基づいて辺を張ればよい。

このように辺を張ることで、元のグラフにおける大小関係を \(O(N \log N)\) 頂点 \(O(N \log N)\) 辺のグラフで表現することができた。

このグラフ上で優先度付きキューを使ってトポロジカルソートすることで、辞書順最小のトポロジカルソート順を得ることができる。(ただし、仮想的な頂点は実際の頂点より先に処理しなければならないことに注意)

計算量はあらかじめ \(R_a\) の順にソートしておくことで空間時間ともに \(O(N \log N)\) を達成できる。