We handle as an exception the case where \(A\) contains at most one \(-1\), and consider other cases.

For the sequence \(A\) (such that \(B\) is lexicographically smallest) after Snuke’s rewriting, there must exist an \(i\) satisfying \(A_i=1\), and let \(p\) be the smallest such \(i\). Then, it can be proved that the only numbers Snuke wrote are \(1\) and \(p\).

We determine \(B_i\) in order of \(i = 1,2, \ldots, N\) according to the following procedure.

Here, if the value of \(p\) is not determined by the end, we need to set \(p\) as the smallest \(i\) such that \(A_i=-1\).

Before entering the phase of minimizing the value of \(p\)

If \(A_i = 1\), then \(p = i\) is determined.

If \(A_i = -1\), set \(A_i = p\) (note that the value of \(p\) itself is not yet determined). Furthermore, if \(i=1\), then \(p=1\) is determined.

If \(A_i \neq -1\) and \(A_{A_i} = p\), then \(B_i = p\), so enter the phase of minimizing \(p\).

If \(A_i \neq -1\) and \(A_{A_i} = -1\), set \(A_{A_i} = 1\).

Phase of minimizing the value of \(p\)

If \(A_i = 1\), then \(p = i\) is determined.

If \(A_i = -1\), set \(A_i = 1\) and determine \(p = i\).

If \(A_i \neq -1\) and \(A_{A_i} = -1\), set \(A_{A_i} = 1\).

After determining the value of \(p\)

If \(A_i = -1\), set \(A_i = p\).

If \(A_i \neq -1\) and \(A_{A_i} = -1\), set \(A_{A_i} = 1\).