1588. 插入还是堆排序

根据维基百科:

插入排序迭代,每次将一个插入元素插入到排好序的输出序列中,每次迭代插入排序都会从输入数据中移除一个元素,并在已排好序的序列中找到它所属的位置,然后将其插入。直到没有输入元素剩余为止。

堆排序将其输入分为已排序和未排序两个区域,并通过提取未排序区域中的最大元素并将其移至已排序的区域来迭代地缩小未排序的区域。它通过使用堆数据结构而非线性时间搜索来找到最大值。

现在,给定初始序列,以及经过某种排序方法多次迭代后的序列,请你判断我们使用的哪一种排序方法。

注意

本题题目描述中曾提到保证答案唯一。

不应该出现诸如下列的样例情况:

9
3 1 2 8 7 9 4 6 0
1 2 3 7 8 9 4 6 0

这种样例情况,无法确定插入排序进行到了第五项还是第六项。

在本网站提供的数据中,并不涉及这种情况。

但是 PAT 官网给出了类似样例,因而可能会出现一些代码在本网站能够 AC,但在 PAT 官网 WA 的情况,特此加以声明。

输入格式

第一行包含整数 $N$,表示序列中整数个数。

第二行包含 $N$ 个整数表示初始序列。

第三行包含 $N$ 个整数表示经过若干次迭代后的序列。

假定排序的目标序列总是递增的。

输出格式

第一行输出 Insertion SortHeap Sort,以指明所采用的具体排序方法。

运用此方法再进行一次迭代,并在第二行输出本次迭代后的序列。

数据保证答案唯一。

数据范围

$1 \le N \le 100$

输入样例1:

10
3 1 2 8 7 5 9 4 6 0
1 2 3 7 8 5 9 4 6 0

输出样例1:

Insertion Sort
1 2 3 5 7 8 9 4 6 0

输入样例2:

10
3 1 2 8 7 5 9 4 6 0
6 4 5 1 0 3 2 7 8 9

输出样例2:

Heap Sort
5 4 3 1 0 2 6 7 8 9