到達可能な順列は，次のように特徴づけられる： 各値 \(v\) について，区間 \([l_v,r_v]\) が存在して，次の条件を満たしている．

• \(v\) の位置が \([l_v,r_v]\) の中に収まっている，をすべての \(v\) について満たしていればそのような順列が作成可能．
• \([l_i,r_i]\) が根付き木の構造をなしている．(\(v\) が大きいほうが先祖になる)

証明とアルゴリズムを同時につくる．

便宜的に，最初は \([i,i]\) という区間が \(i=1,\cdots,N\) について存在しているものとする． \(v\) の昇順に \([l_v,r_v]\) を求めていく．

\(v=m\) まで求めたとしよう． この時点で存在する区間を考えると，いくつかの木ができている． このとき，各木について次の条件が成り立っている．

木の根を区間 \([L,R]\) とする． \([L,R]\) 内にある値を \([L,R]\) 内に収まるような操作だけでどのように並べ変えることができるか考える． \(m\) 以下の値については \([l_i,r_i]\) が求まっており，この区間の中にしか存在できない． そして逆に，これらの条件を満たす並べ方はすべて達成できる． 特に，\(m\) より大きい値は好きなように並び替えることができる．

この条件が成り立つことは後ほど帰納的に確認できる．

さて，このような状況で，\(v=m+1\) が存在可能な区間を求めよう． まず \(v\) が属する木の根に対応する区間 \([L,R]\) をとってくる． あとはこの \(L,R\) を左/右にどれだけ伸ばせるかという問題である．

たとえば \(L\) について考える． \(L\) をまたぐように \(v\) を移動させるためには，以下のような状態が最も望ましい．

位置が \(L\) かそこより右にある値については

• \(v\) ができるだけ \(L\) に近づいている．
• その上で \(m\) 以下の値ができるだけ \(L\) に近づいている

位置が \(L\) より左にある値については

• \(m+1\) より大きい値が一つだけ \(L\) に近づいている
• その上で，\(m\) 以下の値ができるだけ \(L\) に近づいている

このような状況で \(L\) をまたぐ swap ができれば，\(v\) は左側の木に入ることができる． 逆にこれで swap ができない場合は，\(L\) はこれ以上小さくならない．

このような状況，といったが，これをもう少し整理してみる． \(m\) 以下の値については区間がすでに定まっているが，\(L\) のとり方からこの区間が \(L\) をまたぐようなことはない． よって，「\(L\) より右側にあるという条件でできるだけ \(L\) に近づく」ということは，「できるだけ左に置く」ということと同じ． \(L\) の左側についても同様である．

よって，\(m\) 以下の値の位置の分布は，次のようにして求まる． まず，\(m+1\) 以上の値のことを無視してできるだけ \(L\) に近づける． これは上で言ったように，貪欲に左/右に値を置けばよい．

\(L\) をまたぐために，\(v\) が \(L\) に近づいてほしいのだった． 実は「今までの情報から \(v\) が存在しうる最も左の位置」に\(v\) を置けるとわかる． 「今までの情報から \(v\) が存在しうる最も左の位置」とは，\(m\) 以下の値をできるだけ”右”に置いたと仮定したとき，\(L\) かそこより右にあって， \(L\) に最も近い未使用の位置になる． 明らかにここに置くのが最も望ましく，またここに置けるのは木の内部での値の入れ替えが自由であるという仮定による．

ところで，\(m\) 以下の値はできるだけ”左”においてあるので，\(v\) を置くためには調整が必要になる． 例えば，\(v\) を置こうとした場所に \(m\) 以下の値がすでにあると困る．この対処は簡単で，単に \(m\) 以下の値の位置を適切にずらして，\(v\) を置く場所を開けてやればよい． なお，この置き方をしたときの「\(L\) より右にある \(v\) より大きい値であって最も左にあるもの」の位置も簡単にもとまる． それは，\(m\) 以下の値をできるだけ”左”に置いたと仮定したとき，\(L\) かそこより右にあって， \(L\) に \(2\) 番目に近い未使用の位置になる．

\(L\) より左側の様子も同様にして求まる． よって結局，\(L\) をまたぐ swap ができるかどうかを調べるためには，\(m\) 以下の値をできるだけ左/右に置いたと仮定したときの未使用な位置，を保持していればよい． これを set で持てば必要な操作は lower_bound とイテレーターの increment/decrement のみである．

\(L,R\) を可能な限り左右に伸ばして得られる区間が，\([l_v,r_v]\) になる． ここで，木の内部での値の自由な入れ替えもちゃんと行えることが確認できる．

以上を実装すれば \(O(N \log N)\) 時間でこの問題は解ける．

実装例