Count Nodes With Smaller Value
You are given a tree represented by a parent array. The parent array P has length N, where P[i] is the parent of node i. The root node has P[0] = -1. For each node i (from 0 to N-1), you need to count how many other nodes j in the tree have a value j that is strictly smaller than the value i. That is, for each i, compute the count of j such that 0 <= j < i.
Input
The first line contains an integer N (1 <= N <= 1000). The second line contains N integers, the parent array P, where P[0] = -1 and for i > 0, 0 <= P[i] < i.
Output
Print N integers, separated by spaces. The i-th integer (0-indexed) should be the count of nodes j such that j < i.
Constraints
1 <= N <= 1000 P[0] = -1 0 <= P[i] < i for i > 0
Example 1
5 -1 0 0 1 1
0 1 2 3 4
For N=5, node 0 has 0 smaller nodes, node 1 has 1 (node 0), node 2 has 2 (nodes 0, 1), node 3 has 3 (nodes 0, 1, 2), and node 4 has 4 (nodes 0, 1, 2, 3).
Example 2
3 -1 0 1
0 1 2
For N=3, the counts are 0, 1, 2.
Hints
# Read the input from stdin and print the answer.
import sys
def main():
data = sys.stdin.read().split()
# your code here
main()
5 -1 0 0 1 1
3 -1 0 1