题目背景

$xkq_{dalao}$凭借着一手优雅的枚举暴力进入了$\color{Blue}{G} \color{Red}{o} \color{Yellow}{o} \color{Blue}{g} \color{Green}{l} \color{Red}{e}$工作(太强啦!)
$\color{Blue}{G} \color{Red}{o} \color{Yellow}{o} \color{Blue}{g} \color{Green}{l} \color{Red}{e}$为了给他一个表现机会（破产）,决定让他优化自家的搜索引擎（用无脑暴力优化高端算法),这时，他有一个麻烦。
大家都知道像百度、谷歌这样的大数据搜索引擎都有一个排序功能，按照词条的热点度进行排序，可以从大到小，也可以从小到大。
$xkq$疑惑了……

题目

有$n$个词条，第$i$个词条的热点度为$a_i$,请你从大到小排一次，再从小到大排一次。

输入输出格式

输入

共$n+1$行，
第一行一个整数$n$($1 \leq n \leq 10000000$),
以下$n$行，为第$i$个词条的热点度$a_i$($0 \leq a_i \leq 1000000000$)

输出

共两行，第一行，从大到小的热点度排序，第二行，从小到大的热点度排序

样例

Input1

10
1 3 4 5 6 3 2 3 5 2

Output1

6 5 5 4 3 3 3 2 2 1
1 2 2 3 3 3 4 5 5 6

评测时空分配（每单个测试数据)

时间

#1#2#3#4 1s
#5 5s

空间

充足