\(A\) に含まれる \(-1\) が \(1\) 個以下の場合は例外処理し、それ以外の場合を考えます。

すぬけ君が書き換えた後の（\(B\) が辞書順最小となるような）数列 \(A\) に対し、\(A_i=1\) を満たす \(i\) は必ず存在し、そのうち最小の \(i\) を \(p\) とします。このとき、すぬけ君が書いた数は \(1\) と \(p\) のみであることが証明できます。

次の手順に従って \(i = 1,2, \ldots, N\) の順に \(B_i\) を確定していきます。

なお、最後まで \(p\) の値が確定しなかった場合、\(A_i=-1\) である最小の \(i\) を \(p\) とする必要があります。

\(p\) の値を最小化するフェーズに入る前

\(A_i = 1\) の場合、\(p = i\) に確定。

\(A_i = -1\) の場合、\(A_i = p\) とする（\(p\) の値自体はまだ決まっていないことに注意）。さらに、\(i=1\) なら \(p=1\) に確定。

\(A_i \neq -1\) かつ \(A_{A_i} = p\) の場合、\(B_i = p\) なので、\(p\) を最小化するフェーズに入る。

\(A_i \neq -1\) かつ \(A_{A_i} = -1\) の場合：\(A_{A_i} = 1\) とする。

\(p\) の値を最小化するフェーズ

\(A_i = 1\) の場合、\(p = i\) に確定。

\(A_i = -1\) の場合、\(A_i = 1\) とし、\(p = i\) に確定。

\(A_i \neq -1\) かつ \(A_{A_i} = -1\) の場合、 \(A_{A_i} = 1\) とする。

\(p\) の値を確定させた後

\(A_i = -1\) の場合、\(A_i = p\) とする。

\(A_i \neq -1\) かつ \(A_{A_i} = -1\) の場合、\(A_{A_i} = 1\) とする。