Consider creating a tree on the indexes of the array as follows. For an index $i$, let its parent be $j_i + 1$. Note that this means that we'll also need a node $N + 1$, since $j_N + 1 = N + 1$; this node will be the root of the tree.

Let's define the height of a node as the depth of the deepest node minus its own depth. This tree construction is illustrated below for the sample with heights on the left.

3      7
      /|
2    5 6
     | |
1    3 4
    /|
0  1 2

Notice that as we go down the array from index $N$ to index $1$, the heights of the corresponding nodes decrease. This means that the array consists of first the nodes at height $0$, then the nodes at height $1$, etc. Additionally, since each node $i$'s parent is $j_i + 1$, which is the first index whose element $a_{j_i + 1}$ is greater than $a_i + K$, and a node's parent necessarily has height $1$ higher than the height of that node, the nodes at a certain height need to have values that are approximately $K$ higher than the values of the nodes at the immediately lower height.

This suggests that we assign the values of the nodes as $a_i = h_i K + x_i$, where $h_i$ is the height of node $i$ and $x_i$ is some yet to be determined value between $0$ and $K - 1$. Using these values means that $a_i + K = (h_i + 1)K + x_i$, which means that the point at which values go from being less than $a_i + K$ to more than $a_i + K$ occurs at height $h_i + 1$, which is exactly what we want since $i$'s parent, $j_i + 1$, is at height $h_i + 1$.

All that remains is to choose values of $x_i$ appropriately so that that point occurs at exactly the right place inside height $h_i + 1$. This means choosing the $x$ values so that $x_{j_i + 1} > x_i$, but any smaller indexes at height $h_i + 1$ have an $x$ value less than or equal to $x_i$.

We can do this using DFS. We start by assigning the root node $N + 1$ to have $x_{N + 1} = K - 1$, the largest $x$ value possible. Then, it DFSs through its children starting from the largest index and going down. Whenever we reach a node, we assign it the next lower $x$ value, then DFS through its children in decreasing order. This guarantees that every node $i$ has an $x$ value larger than $i$'s children, but all smaller indexes at the same height as $i$ get an $x$ value smaller than $i$'s children, since the DFS reaches them only after searching through all of $i$'s descendants.

Since each node will get a unique $x$ value, we need to set $K = N + 1$ in order to ensure that all $x$ values are between $0$ and $K - 1$. The $x$ values for the sample are illustrated below.

                7
           /---/
          5   6
         /   /
        3   4
     /-/
    1 2

x = 0 1 2 3 4 5 6

As an example of how this construction works, consider index $4$, which has $j_4 = 5$. Its height is $1$ and its $x$ value is $x_4 = 4$, which means that its array value will be $a_4 = (1)K + 4 = (1)(7) + 4$, and $a_4 + K$ will be $(2)(7) + 4$.

Index $5$ is at height $2$ but has the smaller $x$ value $x_5 = 3$, so its array value will be $a_5 = (2)(7) + 3$, which is smaller than $a_4 + K = (2)(7) + 4$. Similarly, index $6$ is at height $2$ and has the larger $x$ value $x_6 = 5$, so its array value will be $a_6 = (2)(7) + 5$, which is larger than $a_4 + K = (2)(7) + 4$. Therefore index $5$ is the largest index $j$ satisfying $a_j \leq a_4 + K$, and so the requirement $j_4 = 5$ is satisfied.

Using these $x$ values, we can calculate our array $a$ along with the choice of $K = N + 1$ to produce a valid construction. Our algorithm simply consists of constructing the tree then performing a DFS to compute the $x$ values as well as the heights. This runs in $O(N)$ time.

The array values for all indexes in the sample are illustrated below.

                                                                     (3)(7) + 6
                                             /----------------------/
                                   (2)(7) + 3             (2)(7) + 5
                                  /                      /
                        (1)(7) + 2             (1)(7) + 4
          /------------/
(0)(7) + 0   (0)(7) + 1

Code:

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class TestsForHaybales {
    static List<Integer>[] children;
    static long[] depths;
    static long[] xs;
    static long x;

    static void dfs(int a) {
        xs[a] = x;
        x--;
        Collections.reverse(children[a]);
        for (int b : children[a]) {
            depths[b] = depths[a] + 1L;
            dfs(b);
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(in.readLine());
        children = new List[n + 2];
        for (int a = 1; a <= n + 1; a++) {
            children[a] = new ArrayList<>();
        }
        StringTokenizer tokenizer = new StringTokenizer(in.readLine());
        for (int a = 1; a <= n; a++) {
            children[Integer.parseInt(tokenizer.nextToken()) + 1].add(a);
        }
        depths = new long[n + 2];
        xs = new long[n + 2];
        x = n;
        dfs(n + 1);
        long k = n + 1;
        StringJoiner joiner = new StringJoiner("\n");
        for (int a = 1; a <= n; a++) {
            long height = depths[1] - depths[a];
            long value = (height * k) + xs[a];
            joiner.add("" + value);
        }
        System.out.println(k);
        System.out.println(joiner);
    }
}