[SHOI2012] 排序

SHOI2012 D2T2

众所周知，1~n 的全排列包含 n!个排列。通常情况下，我们在生成全排列时都按照他们的字典序生成的。而在本题中，我们就将要考虑一种特殊的全排列生成方式。 具体的，生成的全排列的顺序是由一个生成器决定的。 (1) 生成器本身也是一个 1~n 的排列：$a_1$ , $a_2$ , …, $a_n$ 。 (2) 对于两个不相同的 1~n 的 $x_1$ , $x_2$ , …, $x_n$ 、$y_1$ , $y_2$ , …, $y_n$ 排列而言，首先找到最小的 i，使得 $x_{ai}$ 与 $y_{ai}$ 不相等。 (3) 根据(2)中选择的 i，如果 $x_{ai}$ 在排列 $a_1$ , $a_2$ , …, $a_n$ 中排在 $y_{ai}$ 之前，那么 $x_1$ ,$x_2$ , …, $x_n$ 就会在 $y_1$ , $y_2$ , …, $y_n$ 之前生成。 例如，当 n = 3，生成器为 132 时，1~n 的全排列的生成顺序为：123，132，321，312，231，213。 输入一个排列 $x_1$ , $x_2$, …, $x_n$ ，问，哪个生成器能使得这个排列在所有的排列中尽可能早的生成，哪个生成器能使得这个排列在所有的排列中尽可能晚的生成。 如果有多种生成器能达到要求，那么请输出字典序最小的符合要求的生成器。

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

输出的第一行是一个 1~n 的排列，表示让 $x_1$ , $x_2$ , …, $x_n$ 尽早输出的生成器。 输出的第二行是一个 1~n 的排列，表示让 $x_1$ , $x_2$ , …, $x_n$ 尽晚输出的生成器。 如果有多种生成器能达到要求，那么请输出字典序最小的符合要求的生成器。

3
1 3 2

1 2 3
2 1 3

对于 30%的数据，有 n ≤ 10； 对于 50%的数据，有 n ≤ 200； 对于 90%的数据，有 n ≤ 30000； 对于 100%的数据，有 n ≤ 500000。