P5754 [JSOI2010] Ranking

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).

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.

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 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.

### Sample Explanation There are $3$ rankings that satisfy the ordering constraints: ```plain 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