Produce valid student lineup from parent array

You are given a hierarchy of n students represented by a parent array par of length n.

• Students are labeled 1..n .
• par[i] is the parent (mentor/manager) of student i+1 .
• Exactly one student is the root with par[root-1] = -1 .
• For all other students, par[i] is an integer in [1..n] .
• The input is guaranteed to form a valid rooted tree (no cycles, every node reachable from the root).

A valid lineup is an ordering of all students such that each student appears after their parent.

Task: Return the lexicographically smallest valid lineup (compare two lineups by the first position where they differ; the one with the smaller student id is smaller).

Example

Input:

par = [-1, 1, 1, 2, 2, 2, 2]

This means:

• Student 1 is the root.
• Students 2 and 3 report to 1.
• Students 4,5,6,7 report to 2.

One correct output:

[1, 2, 3, 4, 5, 6, 7]

Constraints (assume): 1 <= n <= 2e5.