Description

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

Input Format

第 1 行：一个正整数 n； 
第 2 行：n 个整数，表示树的高度，每个数之间有一空格相隔，树的高度在[0,1000]

Output Format

第 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

Hint

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

Source

南海区镇赛