Background

On Arbor Day, Little L, Little H, and Little X still had to face a busy exam.

After the exam, as usual, they discussed their scores. Little L was very curious, so he asked all $N$ students in the class about their scores. Of course, just as you might expect, nobody wanted to reveal too much: each person only said whose score they were lower than, and some people did not say anything.

Hardworking Little H and lazy Little X each have an “expected ranking” in mind for all students in the class. That is, Little H may think XX should be ranked $1$st, YY should be ranked $2$nd, and so on. But Little X would think XX should be ranked last (the $1$st from the end), YY should be ranked the $2$nd from the end, and so on.

However, ideals and reality always differ. From the information that Little L gathered, XX can no longer be ranked $1$st. Still, Little H believes XX should be ranked as high as possible.

So Little L came up with a question: after Little H and Little X learn the information he gathered, what will their “mental rankings” of the class look like?

Each student’s index is exactly Little H’s mental preference order. In other words, Little H hopes that students with smaller indices will be ranked as high as possible, while Little X hopes that students with smaller indices will be ranked as low as possible (note: this does not mean that students with larger indices should be ranked higher).

Problem 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