合并排序（内存受限版）

Kotlin Hard sorting

任务 «合并排序（内存受限版）»

给定一个整数数组。需要将其按升序排序，仅使用 O(1) 额外内存（即不使用额外的数组或列表）。只允许在原数组中移动元素。请实现一种原地（in-place）且采用迭代方式（自底向上）的归并排序算法。输出排序后的数组，元素之间用空格分隔。

第一行包含一个整数 N (1 ≤ N ≤ 10^5)。第二行包含 N 个以空格分隔的整数。

一行：N个整数，按升序排列，以空格分隔。

输入

1
42

输出

42

输入

6
6 5 4 3 2 1

输出

1 2 3 4 5 6

输入

3.0 4.0

输出

Invalid input

输入

6
4 2 2 8 3 3 1

输出

2 2 3 3 4 8

main.kt