Description

Given an array $A$ of length $N$, where $A_i$ means that the $i$-th student’s score is lower than the $A_i$-th student’s score (equivalently, the $i$-th student is ranked after the $A_i$-th student). Of course, $A_i$ may equal $0$, which means there is no information about the $i$-th student.

You need to obtain an array $H$ of length $N$, representing the class ranking. Among all rankings that satisfy all constraints given by $A_i$, this ranking should be the lexicographically smallest one.

At the same time, you also need to obtain an array $X$, representing the class ranking. Among all rankings that satisfy all constraints given by $A_i$, this ranking should be the lexicographically largest one.

Input Format

The first line contains a positive integer $N$, the number of students in the class.

The second line contains $N$ non-negative integers separated by spaces. The $i$-th number denotes $A_i$.

Output Format

Output two lines. Each line contains $N$ positive integers separated by spaces. The first line is Little H’s mental ranking, and the second line is Little X’s mental ranking.

4
3 0 2 2

3 1 2 4
4 1 3 2

Hint

Sample Explanation

There are $3$ rankings that satisfy the ordering constraints:

4 1 3 2
4 1 2 3
3 1 2 4

Among them, 3 1 2 4 is lexicographically smallest, and 4 1 3 2 is lexicographically largest.

Constraints

For $10\%$ of the testdata, $N\leq 10$.

For $20\%$ of the testdata, $N\leq 20$.

For $40\%$ of the testdata, $N\leq 2\times 10^3$.

For $100\%$ of the testdata, $1 \leq N\leq 2\times 10^5, A_i\leq N$. Among them, the $5$-th testdata group guarantees $N=1.2\times 10^4$.

Translated by ChatGPT 5