長さ \(N+K-1\) の列 \(A\) に対して、長さ \(N+K-1\) のバイナリ列 \(L\) と \(R\) を次のように定義します。

• \(1 \le i \le N+K-1\) について、\(A_i\) より右の直近 \(K-1\) 要素の中（すなわち、範囲 \(A[i+1, \min(i+K-1, N+K-1)]\) の中）に \(A_i\) に等しい要素があれば \(R_i\) は \(1\) とし、なければ \(0\) とする。

• 同様に、\(A_i\) より左の直近 \(K-1\) 要素の中（すなわち、範囲 \(A[\max(1, i - K+1), i-1]\) の中）に \(A_i\) に等しい要素があれば \(L_i\) は \(1\) とし、なければ \(0\) とする。

これらの値について、いくつかの観察を行います。

• \(1 \le i \le N-1\) について、\(B_i - (1 - R_i) = B_{i+1} - (1 - L_{i+K}) = \) (区間 \(A[i+1:i+K-1]\) 上の相異なる要素の個数) が成り立つ。これは \(L_{i+K} - R_i = B_i - B_{i+1}\) と同値である。

• \(B_1 = K - L_1 - L_2 - \ldots - L_K\) である。実際、この区間上の相異なる要素の個数は、\(L_i = 1\) であるような \(1 \le i \le K\) の個数に過ぎない。

• 同様に、\(B_K = K - R_N - R_{N+1} - \ldots - R_{N+K-1}\) である。

ここで、\(R\) が \(1\) であるような位置すべてと、\(L\) が \(1\) であるような位置すべてを考えます。すると、以下が成り立ちます。

• そのような位置の個数は、\(L\) と \(R\) において等しい。\(R\) でのそのような位置を \(X_1, X_2, \ldots, X_T\) とし、\(L\) では \(Y_1, Y_2, \ldots, Y_T\) とする。

• このとき、各 \(i\) について \(1 \le Y_i - X_i \le K-1\) である。

これを確認しましょう。列 \(A\) の任意の要素を考え、その出現位置を \(P_1 < P_2 < \ldots < P_W\) とします。すると、各 \(1 \le i \le W-1\) について、もし \(P_{i+1} - P_i > K-1\) であれば \(R_{P_i} = L_{P_{i+1}} = 0\) となり、そうでなければ \(R_{P_i} = L_{P_{i+1}} = 1\) となります。従って、\(X\) と \(Y\) に現れるすべての「\(1\)」は、\((L_i, R_j)\) という形のペアであって \(1 \le j-i \le K-1\) であるものに分けられます。これらの条件が、\(1\) の位置をソートした後の順番で考えても成り立つことは容易にわかります。

ここで、与えられた列 \(B\) について、上の五つの条件をすべて満たす列 \(L\) と \(R\) が存在すれば、対応する列 \(A\) を構成できるといえます。これは実はとても簡単にわかります。そのような列 \(L, R\) が与えられたとして、\(A\) の要素を一つずつ構成しましょう。\(L_i\) が \(0\) なら、\(A_i\) に直前の \(K-1\) 要素に現れなかった何らかの新しい値を入れます。そうでなければ、いずれかの \(j\) について \(i = Y_j\) です。その場合は、\(A_{Y_j}\) に \(A_{X_j}\) を入れましょう。

さて、そのような列 \(L\) と \(R\) がそもそも存在するかを調べなければなりません。\(L, R\) はどの程度自由に選べるのでしょうか。

もし \(B_i>B_{i+1}\) または \(B_i<B_{i+1}\) であれば、\(R_i\) と \(L_{i+K}\) の値を導けます。もし \(B_i = B_{i+1} = k\) であれば、\(R_i = L_{i+K} = 0\) とするしかありません。以上に該当しなければ、選択の余地があり、両方を \(0\) にするか、両方を \(1\) にするかです。ここで、実は両方を \(1\) にしてよいといえます。

証明: 上の条件をすべて満たすような列 \(L, R\) であって、\(R_i = L_{i+K} = 0\) であるものが存在すると仮定します。\(B_i < K\) より、\(A[i+1:i+K-1]\) に二つの等しい要素 \(A_u, A_v\) が存在し、それらは \(R\) と \(L\) の中で「ペア」となっています。しかし、それならば、\(R_i = L_{i+K} = 1\) とし、\(R\) の中の \(i\) と \(L\) の中の \(v\) をペアにして、\(R\) の中の \(u\) と \(L\) の中の \(i+K\) をペアにすることができます。

\(L_1 + L_2 + \ldots + L_K = B_1 - K\) という条件については、基本的に \(L\) の最初の \(K\) 要素の中の \(1\) の個数を与えられているとみなせます。明らかに、それらの \(1\) は \(L[1:K]\) の末尾に置くのが（条件を満たす上で）最適です。同様に、\(R[N-K+1:N]\) の中に必要な \(1\) は、その先頭に置きます。

よって、題意を満たす列 \(A\) が存在するなら、上の条件がすべて成り立つような何らかの列 \(L\) と \(R\) を求められます。ですから、それらの列を作ってみて、条件が実際に成り立つかを確かめましょう（そしてもし成り立つなら、先に述べたように \(A\) を構成しましょう）。