原地升序堆排序

难度：T2

【知识点：堆排序】

前置知识：本单元此前讲解的状态、边界与实现。

题目描述

将给定整数按从小到大的顺序排列并输出，保留所有重复值。

输入格式

输入$n$及$n$个整数。

输出格式

输出升序数组。

数据范围

$1\le n\le 100000$，整数绝对值≤$10^9$。

样例输入

4
4 1 3 2

样例输出

1 2 3 4

样例输入 2

5
4 1 1 -2 9

样例输出 2

-2 1 1 4 9

样例说明 2

按升序输出，并保留两个 $1$。