明らかに答えは \(Q\) 以下です． そこでまず，答えが \(Q\) になるか否かを判定する方法を考えます．

\(P_1=Q_1\) の場合，この値は終始動かさないべきです． 同様の議論で，\(P,Q\) の共通 prefix は無視してよいことが分かります．以下，\(P_1 < Q_1\) を仮定します．

\(X_i=P^{-1}(Q_i)\) とおきます．つまり，\(Q_i\) の \(P\) 内での位置が \(X_i\) です．

操作を逆順に見て，\(Q\) に対して操作することを考えると，以下の条件を満たす index \(i\) が存在するべきです．

• \(Q_i>Q_{i+1}\)
• \(X_i>X_{i+1}\)

このような \(i\) の最小値を \(Z\) と置きます．

ここで突然ですが，以下の条件を満たす index \(k\) が存在するかどうかを考えます．

• \(k<Z\)
• \(Q_k>Q_{k+1}\)
• \(X_k<X_{k+1}\)
• \(X_i=\min_{k \leq j \leq i} X_j\) を満たすすべての \(i\) (\(k+2 \leq i \leq N\)) に対して，\(Q_{k+1}<Q_i\) が成立

このような \(k\) が存在するとどうなるでしょうか？ まず \(k<Z\) の条件により，index \(k\) 以下での swap は最初はできません． これが可能になるのは，index \(k,k+1\) の swap が起きてからになります． そして，最初に \(k,k+1\) を swap する際の \(Q_{k+1}\) の値の候補が，\(4\) 番目の条件で check している \(Q_i\) です． しかしながら，\(Q_{k+1}<Q_i\) より，このような \(Q_i\) を index \(k+1\) に持ってきた段階で順列全体が元の \(Q\) より辞書順で大きくなってしまいます． つまり，このような \(k\) が存在すると，\(Q \to P\) という操作はできません．

そして逆に，このような \(k\) が存在しない時，\(Q \to P\) という操作が可能であることが証明できます． 手順としては，まず最初に \(Q_Z,Q_{Z+1}\) の swap を行います． その後，各 \(t=Z-1,Z-2,\ldots,1\) に対し，以下の操作を行います．

• \(X_i=\min_{t \leq j \leq i} X_j\) をみたす \(i\) の中で，\(Q_i\) が最小となるものをとり，これを index \(t+1\) まで移動させる．そして，index \(t,t+1\) の swap を行う．

この操作が途中で失敗する状況を考えると，上で定義した \(k\) が存在していることがわかります．

これで，答えが \(Q\) になるかどうかを判定することができました．

\(P\) から始めて \(R\) 以下を通って \(R\) に到達可能，であるような順列 \(R\) を，valid な順列と呼ぶことにします． \(Q\) 以下の valid な辞書順最大順列を求めることが目標です．そのためにまず，\(Q\) の prefix をどこまで実現できるかを計算することが必要です．

長さ \(L\) (以上)の prefix が実現可能であるためには，以下の条件を満たすことが必要です．

• まず \(Z\) を計算する．\(Z<L\) の場合は正しく計算できる．そうでない場合は，\(Z=L\) としておく．
• 上記の条件を満たす \(k\) が存在するかチェックする．ただしチェックの際，index \(L+1\) 以降の値は最も都合のよい形で並んでいると仮定する．つまり，\(k\) が存在しないような並べ方が \(1\) つでも存在すればOKとする．より具体的には，index \(L+1\) 以降は \(X_i\) の降順に並んでいると考えて判定を行う．

この判定が true を返す最大の \(L\) を \(Lmax\) と呼ぶことにします． ここで注意すべきなのは，上の判定は必要条件を述べているのであって，十分条件ではないということです． つまり，真に実現可能な prefix の長さを \(Lreal\) としたとき，即座に分かるのは \(Lreal \leq Lmax\) ということだけです．

\(Lreal\) のことは一旦置いておいて，\(Lmax\) を求めることにしましょう． \(L\) を increment しながら判定を行うことを考えると，以下のようなアルゴリズムになります．

• 今，長さ \(L-1\) の prefix までは判定を終えており，ここに \(Q_L\) を追加しようとしているとする．
• 現在の \(k\) の候補となる index を集めた stack \(S\) を考える． \(S\) の要素 \(s\) は，列の先頭 \(L-1\) 項だけを見た場合に \(k\) としての条件を満たす index である．\(s\) が \(k\) にならないための条件は，ある \(w_s,h_s\) によって表され，これは，\(X_i < h_s\) かつ \(Q_i < w_s\) を満たす \(i\) (\(L \leq i\)) が存在すればよい，という形である． stack の要素は，index の大きいものが top に来るようにしておく． また，弱い条件を課している候補を消すことで，\(w_s,h_s\) の単調性を保つようにしておく．
• \(Q_L\) の追加には，\(2\) 通りの失敗パターンがある．
  • (i) \(X_{L-1}<X_L\) かつ \(Q_{L-1}>Q_L\) のとき: \(k\) の候補として \(L-1\) が新たに追加される．\(L+1\) 項目以降に，\(X_i<X_{L-1}\) かつ \(Q_i<Q_L\) を満たす \(i\) が存在しなければ，この時点で失敗とわかる．
  • (ii) \(X_{L-1}>X_L\) のとき: \(S\) の top の項 \(s\) に注目する．\(Q_L\) の追加によって，\(s\) が \(k\) としての条件を満たすことが確定する場合，失敗とわかる．
• 上記の失敗パターンに含まれない場合は成功と判定し，\(L\) を increment し，適宜 \(S\) も更新する．

先ほど \(Lreal\) の値と \(Lmax\) は異なると書きましたが，実は \(Lreal\) の値は \(Lmax\) から以下のように計算することができます．

• \(Lmax=N\) のとき: これは答えとして \(Q\) が達成可能であることを表す．当然 \(Lreal=N\) である．
• パターン (i) で失敗したとき: \(Lreal=Lmax-1\) である．
• パターン (ii) で失敗したとき: \(Lreal=Lmax\) である．

まずはこの関係を証明します．

パターン (i) で失敗したとします． この時，\(v<Q_{Lmax+1}\) を満たす任意の \(v\) について，\(P^{-1}(v)>X_{Lmax}\) です． よって，\(Lmax+1\) 番目にどの \(v\) を採用したとしても，同じようにパターン (i) で失敗することになります． この時点で \(Lreal \leq Lmax-1\) が分かります．

次に，\(Lreal \geq Lmax-1\) を示します． 今，先頭 \(Lmax-1\) 項は確定しているとします． \(Q_i<Q_{i+1}<\cdots<Q_{Lmax}\) を満たす最小の \(i\) を取り，\(m\) とおきます． \(m=1\) なら，\(Lmax\) 番目に \(P_1\) を置くことで，valid な順列になります． \(1<m\) の時，まだ valid 判定されていないことから，\(X_{m-1}<X_m\) が分かります． ここから \(m-1\) が \(k\) の候補として生きていることが分かります． しかし \(m-1\) は \(k\) になると確定したわけではありません． これは，\(X_i < \min_{m-1 \leq j \leq Lmax-1} X_j\) かつ \(Q_i < Q_m\) を満たす index \(i\) (\(Lmax \leq i \)) の存在を意味しています． このような \(Q_i\) を \(Lmax\) 番目に持ってくることで，valid な順列を得ることができます． これで \(Lreal \geq Lmax-1\) が示され，直ちに \(Lreal=Lmax-1\) が従います．

次に，パターン (ii) で失敗したとします．このケースは，上記パターン (i) の \(m>1\) のケースと同様に考えることで，\(Lreal=Lmax\) が従います．

これで \(Lreal\) を求めることができました． 次に，\(Lreal+1\) 番目の値が何になるか考えます． これは値を \(1\) つずつ試し，それぞれ \(O(1)\) で追加できるかどうかを判定すればよいです． この判定は，\(L\) を increment するときに使ったのと全く同じ判定でよいです． この判定を通った値が実際に valid な順列で使用できることを，\(Lmax+2\) 番目以降の値を具体的に構成することで示します．

\(Lmax+2\) 番目以降の値は，以下の手順で \(1\) つずつ決定していきます．

• 現在の \(S\) の top の要素 \(s\) を考える．現在未使用な \(w_s\) 未満の値の中で，\(P\) での登場が最も早いものを \(v\) とする． 次に採用する値を \(u\) とすると，\(P^{-1}(u) \geq P^{-1}(v)\) が必要となる．そこで，\(P^{-1}(u) \geq P^{-1}(v)\) を満たす最大の \(u\) を採用する．

値を決定するたびに \(S\) を更新するのを忘れないで下さい．

この手順で値を決めていくと，どの失敗パターンにも引っかからないことが確認できます． そして，この構築は明らかに辞書順で最大の valid な順列を達成しています．

以上の操作を実装することで，\(O(N \log N)\) 時間の解法が得られます．

なお，「現在未使用な \(w_s\) 未満の値の中で，\(P\) での登場が最も早いもの」を計算する際，実は”現在未使用な”という条件は気にしなくてもよい，つまり，最初に各 \(w_s\) に対して \(v\) が決定できるということが示せます． writer 解はこの事実を用いて実装を簡略化しています．

解答例(C++)