Cerința

Tocmai s-a lansat un nou joc de computer. Ești un explorator spațial într-un univers cu N planete, fiecare are un teleportor către o altă planetă însemnând că de pe planeta curentă poți merge cătra planeta unde te poți teleporta. Legăturile sunt unidirecționate. Întrebarea este dacă tu acum ai fi pe planeta i, câte rute de teleportare trebuie să folosești astfel încât să ajungi pe o planetă pe care ai mai fost deja. Trebuie calculată pentru fiecare planetă această valoare.

Date de intrare

Programul citește de la tastatură numărul N iar pe următorul rând N numere, al i-elea număr de pe al doilea rând reprezentând planeta pe care poți ajunge cu 1 teleportare de pe planeta i.

Date de ieșire

Programul va afișa pe ecran N numere naturale, al i-elea număr reprezentând răspunsul pentru a i-a planetă.

Restricții și precizări

• 1 ≤ N ≤ 200.000.
• Problema este gândită în stilul ACM adică totul sau nimic la punctaj, motiv pentru care soluții proaste pot lua multe puncte, însă 100p poate obține doar o sursă corectă și eficientă.

Exemplu:

Intrare

5
2 4 3 1 4

Ieșire

3 3 1 3 4

Explicație

Porndind de pe planeta 1 vom avea trasul 1 -> 2, 2 -> 4, 4 -> 1, în total 3 teleportări.