Lexicographical Ranking Assignment

There are N students numbered from 1 to N. You are given a sequence A of length N, where for each student i (1 ≤ i ≤ N), if A_i ≠ 0 then student i has a lower score (or, equivalently, a worse rank) than student A_i. In other words, if A_i ≠ 0 then the rank of student i must be strictly greater than the rank of student A_i (recall that a better rank is represented by a smaller number). If A_i = 0, there is no information regarding student i.

Your task is to assign a rank to every student – that is, produce a permutation H of {1, 2, …, N} – such that for every i with A_i ≠ 0 it holds that

$$H[i] > H[A_i]$$

You need to find two rankings:

1. H: the lexicographically smallest ranking among all valid rankings.
2. X: the lexicographically largest ranking among all valid rankings.

A ranking R = (R[1], R[2], …, R[N]) is lexicographically smaller than another ranking S = (S[1], S[2], …, S[N]) if for some k (1 ≤ k ≤ N) we have R[1] = S[1], R[2] = S[2], …, R[k-1] = S[k-1] and R[k] < S[k].

Hint: The condition H[i] > H[A_i] for all applicable i means that if you view an edge from A[i] to i (whenever A[i] ≠ 0) the ranking ordering of students must be consistent with these precedence constraints. One way to satisfy these is to compute topological orders of the dependency graph. To obtain the lexicographically smallest (or largest) ranking H (when H is considered as an array where the i-th element is the rank of student i), note that if a student appears earlier in the topological order then he gets a smaller ranking number (since we assign ranks in increasing order). Thus, if you always choose the available student with the smallest index when constructing a topological order, you get one valid ranking. Similarly, choosing the available student with the largest index produces the lexicographically largest ranking.

inputFormat

The input consists of two lines. The first line contains a single integer N (the number of students). The second line contains N integers: A₁, A₂, …, A_N, where 0 ≤ A_i ≤ N and if A_i ≠ 0 then student i's rank must be strictly greater than the rank of student A_i.

outputFormat

Output two lines:

1. The first line contains N integers representing the lexicographically smallest valid ranking H for students 1 to N.
2. The second line contains N integers representing the lexicographically largest valid ranking X for students 1 to N.

Both H and X are permutations of {1, 2, …, N} and satisfy for each i with A_i ≠ 0 the inequality

$$H[i] > H[A_i] \quad \text{and} \quad X[i] > X[A_i]. $$

sample

3
0 0 0

1 2 3
3 2 1

</p>