众所周知，$1 \sim n$ 的全排列包含 $n!$ 个排列。通常情况下，我们在生成全排列时都按照他们的字典序生成的。而在本题中，我们就将要考虑一种特殊的全排列生成方式。
具体的，生成的全排列的顺序是由一个生成器决定的。
- 生成器本身也是一个 $1 \sim n$ 的排列：$a_1,a_2, \ldots,a_n$ 。
- 对于两个不相同的 $1 \sim n$ 的 $x_1, x_2,\ldots, x_n$ 、$y_1, y_2, \ldots, y_n$ 排列而言，首先找到最小的 i，使得 $x_{a_i}$ 与 $y_{a_i}$ 不相等。
- 根据 2. 中选择的 $i$，如果 $x_{a_i}$ 在排列 $a_1, a_2, \ldots, a_n$ 中排在 $y_{a_i}$ 之前，那么 $x_1, x_2, \ldots, x_n$ 就会在 $y_1 ,y_2, \ldots,y_n$ 之前生成。
例如，当 $n = 3$，生成器为 132 时，$1 \sim n$ 的全排列的生成顺序为：123，132，321，312，231，213。
输入一个排列 $x_1,x_2, \ldots, x_n$ ，问，哪个生成器能使得这个排列在所有的排列中尽可能早的生成，哪个生成器能使得这个排列在所有的排列中尽可能晚的生成。
如果有多种生成器能达到要求，那么请输出字典序最小的符合要求的生成器。
输入格式
输入的第一行是整数 $n$，第二行是 $1 \sim n$ 的一个排列 $x_1, x_2, \ldots, x_n$ 。
输出格式
输出的第一行是一个 $1 \sim n$ 的排列，表示让 $x_1, x_2, \ldots, x_n$ 尽早输出的生成器。
输出的第二行是一个 $1 \sim n$ 的排列，表示让 $x_1, x_2, \ldots, x_n$ 尽晚输出的生成器。
如果有多种生成器能达到要求，那么请输出字典序最小的符合要求的生成器。
样例数据
样例 1 输入
3 1 3 2
样例 1 输出
1 2 3 2 1 3
子任务
对于 $30\%$ 的数据，有 $n \le 10$；
对于 $50\%$ 的数据，有 $n \le 200$；
对于 $90\%$ 的数据，有 $n \le 30\,000$；
对于 $100\%$ 的数据，有 $n \le 500\,000$。