测试数据来自 oistream/1075

背景

这是一道模板题。

• Idea: 人类
• Data: oistream
• Std: oistream
• 题面: oistream

描述

给定整数序列 \(A=<a_1,a_2,\cdots ,a_n>\)，请对此序列进行处理，使得处理后对于任意的 \(1\leq i\lt j\leq n\)，都有 \(a_i\lt a_j\)。

输入格式

第一行，一个整数 \(n\)。

第二行共有 \(n\) 个数，以空格分隔，表示序列 \(A\)。

输出格式

一行，\(n\) 个数，表示处理后的序列。

样例

样例输入1

5
1 3 2 4 6

样例输出1

1 2 3 4 6

样例解释

无。

数据规模与约定

对于 \(50\%\) 的数据，\(1\leq n\leq 10^4\)

对于 \(100\%\) 的数据，\(1\leq n\leq 10^6\)，对于任意的 \(1\leq i\leq n\)，都有 \(a_i\leq 10^{9}\)。

说明与提示

本题是标准版，\(\mathcal{O}(n^2)\) 的各类算法请左转弱化版。

本题输入输出规模较大，建议采取较快的输入输出方式。