Ви граєте в гру, яка складається з \(n\) планет. Кожна планета має телепорт на іншу планету (або на саму планету).

Ви починаєте на планеті, а потім подорожуєте через телепорти, поки не досягнете планети, яку ви вже відвідували раніше.

Ваше завдання — обчислити кількість телепортацій для кожної планети, якби ви почали з цієї планети.

Обмеження

• \(1≤n≤2⋅10^5\)
• \(1≤t_i ​ ≤n\)

Формат вхідних даних

У першому рядку є ціле число \(n\): кількість планет. Планети пронумеровані \(1,2,…,n\).

У другому рядку \(n\) цілих чисел \(t_1 ​ ,t_2 ​ ,…,t_n\) ​ : для кожної планети пункт призначення телепортатора. Можливо, що \(t_i ​ =i\).

Формат вихідних даних

Вивести \(n\) цілих чисел згідно з постановкою задачі.

Приклад вхідних даних

5
2 4 3 1 4

Приклад вихідних даних

3 3 1 3 4