题目描述

众所周知，$1$ 到 $n$ 的全排列包含 $n!$ 个排列。通常情况下，我们在生成全排列时都按照他们的字典序生成的。而在本题中，我们就将要考虑一种特殊的全排列生成方式。

具体的，生成的全排列的顺序是由一个生成器决定的。

1. 生成器本身也是一个 $1$ 到 $n$ 的排列：$a_1,a_2,\dots,a_n$。
2. 对于两个不相同的 $1$ 到 $n$ 的 $x_1,x_2,\dots,x_n$、$y_1, y_2,\dots,y_n$ 排列而言，首先找到最小的 $i$，使得 $x_ai$ 与 $y_ai$​ 不相等。
3. 根据 $(2)$ 中选择的 $i$，如果 $x_ai$​ 在排列 $a_1, a_2,…,a_n$ 中排在 $y_ai$​ 之前，那么 $x_1,x_2,\dots,x_n$ 就会在 $y_1, y_2,\dots,y_n$ 之前生成。

例如，当 $n=3$，生成器为 $132$ 时，$1$ 到 $n$ 的全排列的生成顺序为：$123,132,321,312,231,213$。

输入一个排列 $x_1,x_2,\dots,x_n$，问，哪个生成器能使得这个排列在所有的排列中尽可能早的生成，哪个生成器能使得这个排列在所有的排列中尽可能晚的生成。

如果有多种生成器能达到要求，那么请输出字典序最小的符 $(1)$ 要求的生成器。

输入格式

输入的第一行是整数 $n$，第二行是 $1$ 到 $n$ 的一个排列 $x_1,x_2,\dots,x_n$。

输出格式

输出的第一行是一个 $1$ 到 $n$ 的排列，表示让 $x_1,x_2,\dots,x_n$ 尽早输出的生成器。

输出的第二行是一个 $1$ 到 $n$ 的排列，表示让 $x_1,x_2,\dots,x_n$ 尽晚输出的生成器。

如果有多种生成器能达到要求，那么请输出字典序最小的符合要求的生成器。

3
1 3 2

1 2 3
2 1 3

提示

对于 $30\%$ 的数据，有 $n\le10$；

对于 $50\%$ 的数据，有 $n\le200$；

对于 $90\%$ 的数据，有 $n\le30000$；

对于 $100\%$ 的数据，有 $n\le500000$。