Description

As is well known, the set of all permutations of $\{1, 2, \dots, n\}$ contains $n!$ permutations. Normally, when we generate all permutations, we list them in lexicographic order. In this problem, we consider a special way of generating all permutations.

Specifically, the generation order is determined by a generator.

(1) The generator is itself a permutation of $\{1, 2, \dots, n\}$: $a_1$, $a_2$, …, $a_n$.

(2) For two distinct permutations of $\{1, 2, \dots, n\}$, $x_1$, $x_2$, …, $x_n$ and $y_1$, $y_2$, …, $y_n$, first find the smallest $i$ such that $x_{a_i}$ and $y_{a_i}$ are not equal.

(3) According to the $i$ chosen in (2), if $x_{a_i}$ comes before $y_{a_i}$ in the permutation $a_1$, $a_2$, …, $a_n$, then $x_1$, $x_2$, …, $x_n$ will be generated before $y_1$, $y_2$, …, $y_n$.

For example, when $n = 3$ and the generator is 132, the generation order of all permutations of $\{1, 2, \dots, n\}$ is: 123, 132, 321, 312, 231, 213.

Given a permutation $x_1$, $x_2$, …, $x_n$, determine which generator makes this permutation appear as early as possible among all permutations, and which generator makes it appear as late as possible.

If multiple generators satisfy the requirement, output the lexicographically smallest one.

Input Format

The first line contains an integer $n$. The second line contains a permutation $x_1$, $x_2$, …, $x_n$ of $\{1, 2, \dots, n\}$.

Output Format

The first line outputs a permutation of $\{1, 2, \dots, n\}$, representing a generator that makes $x_1$, $x_2$, …, $x_n$ appear as early as possible.

The second line outputs a permutation of $\{1, 2, \dots, n\}$, representing a generator that makes $x_1$, $x_2$, …, $x_n$ appear as late as possible.

If multiple generators satisfy the requirement, output the lexicographically smallest one.

3
1 3 2

1 2 3
2 1 3

Hint

Constraints

• For 30% of the testdata, $n \le 10$.
• For 50% of the testdata, $n \le 200$.
• For 90% of the testdata, $n \le 30000$.
• For 100% of the testdata, $n \le 500000$.

Translated by ChatGPT 5