题目背景

\(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

空间

充足