题目描述

小顶堆是一种特殊的完全二叉树，它的每个父节点的值都小于或等于其左右子节点的值。请你完成以下任务：

1. 构建一个小顶堆，支持插入若干整数；
2. 完成堆的构建后，依次输出堆顶元素（最小值）并删除堆顶，直到堆为空。

堆的操作规则：

• 插入元素时，将元素添加到堆的末尾，然后向上调整（上浮），确保父节点值 ≤ 子节点值；
• 删除堆顶时，将堆最后一个元素移到堆顶，然后向下调整（下沉），确保小顶堆性质。

输入描述

第一行输入一个整数 n（1 ≤ n ≤ 100），表示要插入堆的元素个数； 第二行输入 n 个整数（范围：0 ≤ 数值 ≤ 1000），表示要插入堆的元素。

输出描述

输出若干行，每行一个整数，表示依次删除堆顶的结果（即按从小到大的顺序输出所有元素）。

输入样例

5
8 3 5 1 9

输出样例

1
3
5
8
9

数据范围

• 1 ≤ n ≤ 100
• 0 ≤ 插入的数值 ≤ 1000