出力すべき列 \(B\) について、\(B _ 1\) の値を決定することを考えます。

\(f(x)\ (1\leq x\leq M)\) を、\(A _ i=x\) を満たす最大の \(i\) として定めます。
\(\displaystyle r\coloneqq\min _ {1\leq x\leq M}f(x)\) について、\(B _ 1\) は \(A _ 1,A _ 2,\ldots,A _ r\) のいずれかであることが示せます （もしそうでなければ、\(B\) は \(A _ {\gt r}\coloneqq(A _ {r+1},A _ {r+2},\ldots,A _ N)\) の部分列ですが、\(A _ {\gt r}\) の要素に \(A _ r\) が存在しないので、\(B\) の条件に反します）。

逆に、\(A _ i\ (1\leq i\leq r)\) のいずれを \(1\) 項目にもつ長さ \(M\) の部分列であって、\(1,2,\ldots,M\) をちょうど \(1\) 回ずつ含むようなものが存在します。 具体的に、すべての \(x\neq A _ i\) について \(A _ {f(x)}\) を含むような部分列が条件を満たします。

よって、\(B _ 1=A _ l=\displaystyle\min _ {1\leq i\leq r}A _ i\) です。 \(l\) は \(A _ j=\displaystyle\min _ {1\leq i\leq r}A _ i\) を満たす最小の整数 \(j\) としてよいです。

（要素に関して適切な読み替えののち、）次のような列について同様の問題を解くことを繰り返せば、\(B\) の要素をすべて決定することができます。

• \(A\) の先頭 \(l\) 項を取り除き、さらに\(A _ i=B _ 1\) をみたす要素すべてを取り除いた列

列に対するこの操作は、優先度付きキューやセグメント木を用いることでシミュレーションできます。

優先度付きキューの場合、\((A _ i,i)\) を管理することとすると、

• 先頭 \(r\) 個の最小値を求めるには、数列の先頭 \(r\) 項を優先度付きキューに入れてそれらの最小値を得ればよいです。
• \(A\) の先頭 \(l\) 項を取り除くことや、特定の値と等しい \(A _ i\) を取り除くことは、優先度付きキューの先頭が条件を満たしている限り優先度付きキューから要素を取り除き続けることで実現できます。

セグメント木の場合、同様にして

• 特定の値と等しい \(A _ i\) を取り除くことは、取り除いた時点でその \(A _ i\) と等しい値をすべて \(\infty\) に書き換えることで可能です。
• 先頭 \(r\) 個の最小値は、書き換えを終えた列における区間最小値になっているので、これを計算すればよいです。

いずれも時間計算量は \(O(N\log N)\) となり、十分高速です。