As is well known, there are $n!$ permutations of $1 \sim n$. Usually, we generate all permutations in lexicographical order. In this problem, we consider a special way of generating permutations.

Specifically, the order of the generated permutations is determined by a generator.

1. The generator itself is a permutation of $1 \sim n$: $a_1, a_2, \ldots, a_n$.
2. For two distinct permutations $x_1, x_2, \ldots, x_n$ and $y_1, y_2, \ldots, y_n$, first find the smallest $i$ such that $x_{a_i} \neq y_{a_i}$.
3. Based on the $i$ chosen in step 2, if $x_{a_i}$ appears before $y_{a_i}$ in the permutation $a_1, a_2, \ldots, a_n$, then $x_1, x_2, \ldots, x_n$ is generated before $y_1, y_2, \ldots, y_n$.

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

Given a permutation $x_1, x_2, \ldots, 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 there are multiple generators that satisfy the requirement, output the lexicographically smallest one.

Input

The first line contains an integer $n$. The second line contains a permutation of $1 \sim n$: $x_1, x_2, \ldots, x_n$.

Output

The first line should contain a permutation of $1 \sim n$ representing the generator that makes $x_1, x_2, \ldots, x_n$ appear as early as possible.

The second line should contain a permutation of $1 \sim n$ representing the generator that makes $x_1, x_2, \ldots, x_n$ appear as late as possible.

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

Examples

Input 1

3
1 3 2

Output 1

1 2 3
2 1 3

Subtasks

For $30\%$ of the data, $n \le 10$.

For $50\%$ of the data, $n \le 200$.

For $90\%$ of the data, $n \le 30\,000$.

For $100\%$ of the data, $n \le 500\,000$.