\(S=\sum_{1 \leq i \leq N} A_i\) とおきます．

まず条件を満たす数列が存在するかどうかを考えます． 最終的な数列を長さ \(Q,K,K\cdots,K\) のブロックに分けることにします．なお，\(1 \leq Q \leq K\) とすることで，この分け方は一意です． ブロックの個数を \(P\) とおきます．

まず，どのブロックについても，そのブロック内の値はすべて異なる必要があります．よって，すべての \(1 \leq i \leq N\) について，\(A_i \leq P\) が必要です． また，\(A_i =P\) を満たす \(i\) の個数が \(Q\) 以下である必要もあります．

逆にこれらの条件を満たす場合，条件を満たす数列が存在します． 以下，実際に辞書順最小の数列を構成する手順を示すことで，この事実を示します．

各 \(0 \leq i \leq N-1\) について，後ろ \(N-i\) 項を長さ \(K\) ずつのブロックに分解していった時，余る部分の長さを \(Q_i\)，ブロックの個数を \(P_i\) で表すことにします．特に，\(Q_0=Q,P_0=P\) です．

条件を満たす辞書順最小の数列は，次の手順で得ることができます．

• \(ans=()\) とし，これに値を追加していく．
• 各 \(i=0,1,\cdots,N-1\) について，以下を行う．
  • (a): \(A_v=P_i\) を満たす \(v\) が \(Q_i\) 個あるなら，それらのうち \(ans\) の後ろ \(K-1\) 項に登場しないものの中で，最小の値を \(m\) とする．
  • (b): そうでないなら，\(A_v \geq 1\) を満たす \(v\) のうち，\(ans\) の後ろ \(K-1\) 項に登場しないものの中で，最小の値を \(m\) とする．
  • \(ans\) の最後尾に \(m\) を追加し，\(A_m\) の値を \(1\) 減らす．

この手順が正常に終了するためには，以下のことを示す必要があります．

• (1): 各 \(i\) について，操作を行う前の段階で，\(\max A_v \leq P_i\) である．また，\(A_v=P_i\) を満たす \(v\) の個数は \(Q_i\) 以下である．
• (2): 各 \(i\) について，条件を満たす値が \(1\) つ以上存在し，\(m\) が定義できる．

逆に，この手順が正しく終了するならば，その結果は明らかに辞書順最小です．よって，あとは (1) と (2) を示します．

(1) に関しては，\(i=x\) で成立するなら \(i=x+1\) でも成立することがすぐにわかります．\(i=0\) で成立するので，帰納法より示されました．

(2) を示します．今，\(i=x\) において，条件を満たす \(m\) が \(1\) つもない，という状況が今起こったとします．

• (a) で起こった時: \(ans\) の後ろ \(K-1\) 項に，\(A_v=P_i\) を満たす \(v\) が全て含まれていることになる．しかしこの場合，\(i=x-(K-1)\) の段階で (1) が満たされていないことになり，矛盾が生じる．

• (b) で起こった時: \(A_v \geq 1\) を満たす \(v\) の個数は \(K-1\) 以下である．ここで (1) より，\(N-i \leq K-1\) が従い，更に \(P_i=1\) であるとわかる．すると結局このパターンは (a) に分類されるとわかる．

なお，厳密には \(ans\) の長さが \(K-1\) 未満である場合も考える必要もありますが，これも全く同様の議論で処理できます． これで上記の手順の正当性が証明できました．

上の手順を素直に実装すれば \(O(SN)\) 時間になり，十分高速です．