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$?

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

The second line contains $n - 1$ integers $p_2$, $p_3$, ..., $p_n$ ($1 \le 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 $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$.