排序

给定一个 $\{1,2,\ldots,n\}$ 的排列 $a$。将每个环表示为

$$C=(c_0,c_1,\ldots,c_{L-1}),$$

其中，$c_0$ 是该环中的最小元素，且 $c_{i+1}=a_{c_i}$，下标在环内循环。

输出的第一行按如下方式构造：将所有环按照环长升序排列；环长相同时，按照 $c_0$ 升序排列。随后依次连接各环中的元素并输出。

输出的第二行按如下规则构造。首先维护一个有序对序列 $P$。

• 对所有长度为大于 $1$ 的正偶数的环，按照环长降序、$c_0$ 升序的顺序处理。对于长度为 $L$ 的环，依次向 $P$ 中加入

  $$(c_0,c_1),(c_{L-2},c_{L-1}),(c_{L-4},c_{L-3}),\ldots$$

• 对所有长度大于 $1$ 的奇环，初始按照环长降序、$c_0$ 升序的顺序编号。反复选择当前未配对元素数最多的环；若有多个环满足条件，则选择初始编号较小的环。

  对于每个奇环，第一次被选择时向 $P$ 中加入 $(c_0,c_1)$，以后被选择时依次加入

  $$(c_{L-2},c_{L-1}),(c_{L-4},c_{L-3}),\ldots$$

  每次加入一个有序对后，从该环中去掉对应的两个元素。若环中仍至少剩下 $3$ 个元素，则该环继续参与选择。最终，每个奇环都恰好剩下元素 $c_2$。

• 构造序列 $Q$：首先按照上述奇环的初始顺序，将每个奇环剩下的 $c_2$ 放入 $Q$；然后按照元素值降序，将所有不动点放入 $Q$。

  对于

  $$i=0,\ldots,\left\lfloor\frac{|Q|}{2}\right\rfloor-1,$$

  向 $P$ 中加入

  $$\left(Q[|Q|-1-i],Q[i]\right).$$

• 设第二行的排列为 $b$。对于 $P$ 中第 $k$ 个有序对 $(x,y)$，其中 $k$ 从 $1$ 开始，令

  $$b_k=x,\qquad b_{n+1-k}=y.$$

  若 $|Q|$ 为奇数，再令

  $$b_{\left\lfloor n/2\right\rfloor+1} = Q\left[\left\lfloor |Q|/2\right\rfloor\right].$$

最后输出 $b_1,b_2,\ldots,b_n$。

输入格式

第一行输入一个整数 $n$。

第二行输入 $n$ 个整数 $a_1,a_2,\ldots,a_n$，保证它们构成 $\{1,2,\ldots,n\}$ 的一个排列。

输出格式

输出两行，每行包含 $n$ 个整数，分别表示按上述规则构造的第一行序列和第二行排列。

样例输入

3
1 3 2

样例输出

1 2 3
2 1 3

数据范围

• $1\le n\le 5\times 10^5$。

来源与许可

本题题面与测试数据整理自 BZOJ。

样例 1

输入

3
1 3 2

输出

1 2 3
2 1 3