Once the piece reaches a cell \(i\) with \(A _ i=i\), it does no longer move from there. Until then the piece advances by at least one cell in one move, but such an event occurs at most \((N-i)\) times starting from cell \(i\). Since \(N\leq10 ^ {100}\), “performing the operation \(10 ^ {100}\)” is essentially “performing the operation until the piece can no longer move.”

Therefore, the following algorithm outputs a correct answer:

• For \(i=1,2,\ldots,N\) in order, do the following:
  1. Initialize \(\operatorname{ans}\leftarrow i\).
  2. While \(\operatorname{ans}\neq A _ {\operatorname{ans}}\), repeatedly set \(\operatorname{ans}\leftarrow A _ {\operatorname{ans}}\).
  3. Print \(\operatorname{ans}\).

The repetition in step 2. is iterated at most \(N-i\) times for each \(i\). Thus, the worst time complexity of this algorithm is \(\Theta(N ^ 2)\), so implementing and submitting this algorithm will result in exceeding the time limit.

However, if you try to find \((\operatorname{ans} _ 1,\operatorname{ans} _ 2,\ldots,\operatorname{ans} _ N)\) from the bottom, the later results can be reused.

• For \(i=N,N-1,\ldots,2,1\), do the following:
  1. Initialize \(\operatorname{ans} _ i\leftarrow i\).
  2. If \(\operatorname{ans} _ i\neq A _ {\operatorname{ans} _ i}\), set \(\operatorname{ans} _ i\leftarrow\operatorname{ans} _ {A _ i}\).
• For each \(i=1,2,\ldots,N\), print \(\operatorname{ans} _ i\).

This way, the worst time complexity is reduced to \(\Theta(N)\), which is fast enough to find the answer.

The following is sample code:

#include <iostream>
#include <vector>
#include <ranges>

int main() {
    using namespace std;
    int N;
    cin >> N;

    vector<int> A(N);
    for (auto&& a : A) {
        cin >> a;
        --a; // turn it into 0-based indexing
    }

    vector<int> ans(N);
    for (int i : views::iota(0, N) | views::reverse) { // Find the final destination in descending order
        if (i == A[i]) { // if you are stuck at there
            ans[i] = i; // that cell is the answer
        } else { // if you will leave
            ans[i] = ans[A[i]]; // the answer starting from the cell you moved into is the answer
        }
    }

    for (int a : ans) {
        // turn to 1-based indexing and print
        cout << a + 1 << " ";
    }
    cout << endl;

    return 0;
}