問題文の条件を満たす入力に対し解が必ず存在することを，\(N\) に関する帰納法で証明すると同時に，辞書順最小の \(P\) の構成を与えます．

数列の値を先頭から決めていくことにします．

まず，\(K=1\) だった場合，\(P=(N,N-1,N-2,\cdots,1)\) とする以外に解は存在しません．

\(K \geq 2\) の時を考えます． \(A_1=1\) のときは，\(P_1=1\) とすればよいです． あとは，\((P_2,P_3,\cdots,P_N)\) の値については，再帰的に決定することにします．つまり，\((A_2-1,A_3-1,\cdots,A_K-1)\) が入力として与えられた場合の解を求め（これは帰納法の仮定より可能），その値 \(1\) ずつ増やしたものを採用すればよいです．

\(A_1 > 1\) のときを考えます． このとき，\(P_1=A_1\) となります． もし \(P_1 < A_1\) であると，\(P_1<A_1<A_2<\cdots<A_K\) が \(P\) の部分列になってしまい，\(A\) が LIS であるという条件を満たしません． また逆に，\(P_1=A_1\) である解は，以下で示すように必ず存在するため，辞書順最小の \(P\) では必ず \(P_1=A_1\) が成立します．

次に，\(P_2=1\) となります． もしこれを満たす解が存在するなら，辞書順最小は明らかに達成しています． よって，解が存在することを示します．

\((2,3,\cdots,A_1-1,A_1+1,\cdots,N)\) の順列 \((P_3,P_4,\cdots,P_N)\) であって，LIS が \((A_2,A_3,\cdots,A_K)\) であるものが存在することは，帰納法の仮定より示せます． そして，こうして得た \(P\) の LIS の長さは確かに \(K\) に一致します．これは，\(P_1 >P_2\) であり，また\(P_2\) を使う単調増加な部分列の長さが \(1+(K-1)=K\) であるためです． もちろん，\(P\) は \(A\) を部分列として含むため，条件を満たします． また，\((P_3,P_4,\cdots,P_N)\) の値を辞書順最小にすることで，\(P\) 全体も辞書順最小を達成します．

よって，上で示した手順にそって，問題を再帰的に解くことができます． 実際の実装では，再帰関数を呼ぶのではなく，未使用の値のリストを管理するほうが簡単です． 計算量は全体で \(O(N)\) になります．