Planets Cycles

#include <bits/stdc++.h>
using namespace std;

// ----------- define --------------
#define int long long
#define vi vector<int>
#define ii pair<int,int>
#define fi first
#define sc second
#define stoi stoll
#define popcnt __builtin_popcount
#define getBit(x, k) ((x >> k) & 1)
#define all(x) (x).begin(),(x).end()
// ---------------------------------

void Main() {
  int n; cin >> n;
  vector<int> a(n);
  for (auto &i : a) {
    cin >> i;
    i--;
  }
  vector<int> d(n), res(n);
  for (int i = 0; i < n; i++) {
    if (!d[i]) {
      map<int, int> m;
      vector<int> s;
      int j = i, c = 0;
      while (!d[j]) {
        m[j] = ++c;
        s.push_back(j);
        d[j] = 1;
        j = a[j];
      }
      if (m.count(j)) {
        int r = c - m[j] + 1;
        while (s.size() && m[s.back()] >= m[j]) {
          res[s.back()] = r;
          s.pop_back();
        }
      }
      while (s.size()) {
        res[s.back()] = res[a[s.back()]] + 1;
        s.pop_back();
      }
    }
  }
  for (auto &i : res) cout << i << ' ';
  cout << '\n';
}

signed main() {
#ifdef _DEBUG
  // freopen("in" , "r", stdin );
  cerr << "- ---- -- ----- <3\n";
#endif
  cin.tie(0)->sync_with_stdio(0);
  int T = 1;
  // cin >> T;
  while (T--) Main();
}