If we follow the sequence \(i \to P_i \to P_{P_i} \to \cdots\), we eventually reach \(1\). Let the depth \(d_i\) of \(i\) be the number of \(\to\) required to reach \(1\) from \(i\).

For each \(j\) \((0 \leq j < N)\), let \(B_j\) be the sum of \(A_i\) over all \(i\) such that \(d_i=j\).

Firstly, \(A_1=B_0\). Also, one operation can be expressed as \(B_{j} \mathrel{+}=B_{j+1}\) (\(0 \leq j < N-1\)).

If all \(B_j\) are \(0\), then no matter how many times we operate, \(B_0\) remains \(0\), so the answer is 0.

Let’s assume there is a non-zero \(B_j\). Now, let’s take the largest \(j\) such that \(B_j \neq 0\) and call it \(k\).

Consider the case where \(B_k>0\). First, since \(B_j\) (\(j>k\)) are all \(0\), the value of \(B_k\) is constant. In particular, it is always positive. Next, consider \(B_{k-1}\). This value increases by \(B_k\) with each operation, so even if the initial value is negative, after a sufficient number of operations, it will always be positive. Next, consider \(B_{k-2}\). From the previous discussion, after a sufficient number of operations, \(B_{k-1}\) will always be positive. Since this \(B_{k-1}\) is added to \(B_{k-2}\), eventually \(B_{k-2}\) will also become positive. Repeating this argument, we can see that after a sufficient number of operations, even \(B_0\) will become positive. Therefore, in this case, the answer is +.

The case where \(B_k<0\) can be discussed similarly, and we can see that the answer is -.

Here, we used the expression “a sufficient number of times,” but if we properly calculate, we can see that \(10^{100}\) is sufficient. It can be done by calculating the contribution of each \(A_i\) using binomial coefficients, although the details are omitted.

If we implement the above judgment as is, we can solve the problem in \(O(N)\) time.

Sample Solution