Festival Peak Stalls

The first line of input contains an integer N, the number of nodes.

The second line contains N space-separated integers, representing the parent of each node from 0 to N-1.

For each depth from 0 to the maximum depth of the tree, print a line in the format: Depth D : C

D is the depth, and C is the count of nodes at that depth.

The output must be ordered by depth, starting from 0.

The interval is inclusive of the start time and exclusive of the end time ([start, end)). This means a stall that ends at hour 5 and another that starts at hour 5 are not operating simultaneously.

Sample Input 1:

3
2 5
1 4
3 7

Sample Output 1:

3

Explanation for Sample 1:

Let's trace the number of active stalls over time:
- Hour 1: Stall `[1, 4)` opens. Active stalls: 1.
- Hour 2: Stall `[2, 5)` opens. Active stalls: 2.
- Hour 3: Stall `[3, 7)` opens. Active stalls: 3. This is the peak.
- Hour 4: Stall `[1, 4)` closes. Active stalls: 2.
- Hour 5: Stall `[2, 5)` closes. Active stalls: 1.
- Hour 7: Stall `[3, 7)` closes. Active stalls: 0.
The maximum number of stalls operating at once was 3.<br>

Sample Input 2:

3
1 5
5 10
10 15

Sample Output 2:

1

Explanation for Sample 2:

The intervals `[1, 5)`, `[5, 10)`, and `[10, 15)` "touch" at the boundaries but do not overlap.
- At `time=5`, the first stall closes just as the second one opens, so only one is considered active.
- The maximum number of stalls active at any single moment is 1.

Expected Time Complexity:

The expected time complexity is O(N log N).

Constraints:

1 <= N <= 10^5
0 <= start < end <= 10^9

Time limit: 1sec