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); } }