1056_D. Decorate Apple Tree_5132
There is one apple tree in Arkady's garden. It can be represented as a set of junctions connected with branches so that there is only one way to reach any junctions from any other one using branches. The junctions are enumerated from 1 to n, the junction 1 is called the root.

A subtree of a junction v is a set of junctions u such that the path from u to the root must pass through v. Note that v itself is included in a subtree of v.

A leaf is such a junction that its subtree contains exactly one junction.

The New Year is coming, so Arkady wants to decorate the tree. He will put a light bulb of some color on each leaf junction and then count the number happy junctions. A happy junction is such a junction t that all light bulbs in the subtree of t have different colors.

Arkady is interested in the following question: for each k from 1 to n, what is the minimum number of different colors needed to make the number of happy junctions be greater than or equal to k?

Input

The first line contains a single integer n (1 ≤ n ≤ 10^5) — the number of junctions in the tree.

The second line contains n - 1 integers p_2, p_3, ..., p_n (1 ≤ p_i < i), where p_i means there is a branch between junctions i and p_i. It is guaranteed that this set of branches forms a tree.

Output

Output n integers. The i-th of them should be the minimum number of colors needed to make the number of happy junctions be at least i.

Examples

Input


3
1 1


Output


1 1 2 


Input


5
1 1 3 3


Output


1 1 1 2 3 

Note

In the first example for k = 1 and k = 2 we can use only one color: the junctions 2 and 3 will be happy. For k = 3 you have to put the bulbs of different colors to make all the junctions happy.

In the second example for k = 4 you can, for example, put the bulbs of color 1 in junctions 2 and 4, and a bulb of color 2 into junction 5. The happy junctions are the ones with indices 2, 3, 4 and 5 then.
from sys import stdin
from collections import *


class graph:
    # initialize graph
    def __init__(self, gdict=None):
        if gdict is None:
            gdict = defaultdict(list)
        self.gdict, self.edges, self.l = gdict, [], defaultdict(int)

    # add edge
    def addEdge(self, node1, node2, w=None):
        self.gdict[node1].append(node2)
        self.gdict[node2].append(node1)

    def subtree(self, v):
        queue, visit, ans = deque([v]), [0] * (n + 1), [[v, 0]]
        visit[v], nodes = 1, [0] * (n + 1)

        while queue:
            s = queue.popleft()

            for i in self.gdict[s]:
                if not visit[i]:
                    queue.append(i)
                    visit[i] = 1
                    ans.append([i, s])

        for i, j in ans[::-1]:
            if not nodes[i]:
                nodes[i] = 1

            nodes[j] += nodes[i]

        print(' '.join(map(str, sorted(nodes[1:]))))


n, a = int(input()), [int(x) for x in stdin.readline().split()]
g = graph()
for i in range(2, n + 1):
    g.addEdge(i, a[i - 2])

g.subtree(1)
