说明

A 城市，新修建了一条迎宾大道，这是一条关系到城市形象的样板路，为了迎接全国文明城市的检查， 要求植树部门在迎宾大道两旁（南北两旁）种上树，并使越高的树尽量越靠近城区中心，分别种在迎宾大 道的两旁，种树规则：先选第 1 高的树种在大道的南边第 1 个位置，再选第 2 高的树种在大道的北边第 1个位置，又选第 3 高的树种在大道的南边第 2 个位置，又选第 4 高的树种在大道的北边第 2 个位置……以 此类推，直到把所有树种完。

如图所示：

现有 n 棵要植的树，植树部门请你帮忙将这 n 棵树由高到低排好序，分别安排好南北两旁所种的树。

输入格式

第 1 行：一个正整数 n；

第 2 行：n 个正整数，表示树的高度，每个数之间有一空格相隔，树的高度不超过 1000。

输出格式

第 1 行：表示南边所植的树的高度，每个数之间有一空格相隔(由高到低)；

第 2 行：表示北边所植的树的高度，每个数之间有一空格相隔(由高到低)。

样例

11
1 23 9 26 98 46 26 26 100 100	9

100 98 26 26 9 1
100 46 26 23 9

提示

【数据规模】对于 80%数据，1≤n≤5000；对于 100%数据，1≤n≤3000000；