Halloween Candy Collection

In Wisconsin every year, the cows celebrate the USA autumn holiday of Halloween by dressing up in costumes and collecting candy that Farmer John leaves in the N stalls (numbered from 1 to N). Farmer John has assigned a 'next stall number' on stall i (denoted as \(next_i\)) such that \(1 \leq next_i \leq N\). Each cow i starts at stall i and follows the chain given by the next stall numbers. The cow stops when she visits a stall she has already visited.

Your task is to compute, for each cow, the number of unique stalls she visits before stopping her candy collection.

Constraints: \(1 \leq N \leq 100,000\).

inputFormat

The first line contains a single integer N, the number of stalls.

The second line contains N space-separated integers where the i-th integer is \(next_i\) which represents the next stall number to visit from stall i.

outputFormat

Output a single line with N space-separated integers. The i-th integer should be the number of unique stalls cow i visits before she returns to a stall she already visited.

sample

4
1 3 2 3

1 2 2 3