Merge sort with memory constraint

Kotlin Hard sorting

Task «Merge sort with memory constraint»

Given an array of integers, it is necessary to sort it in ascending order using only O(1) extra memory (i.e., without using additional arrays or lists). Elements may only be rearranged within the original array. Implement an in-place merge sort algorithm using an iterative (bottom-up) approach. Output the sorted array separated by spaces.

Input Format

The first line contains an integer N (1 ≤ N ≤ 10^5). The second line contains N integers separated by spaces.

Output Format

One line: N integers, sorted in ascending order, separated by spaces.

Examples

Example 1

INPUT

1
42

OUTPUT

42

Example 2

INPUT

6
6 5 4 3 2 1

OUTPUT

1 2 3 4 5 6

Example 3

INPUT

3.0 4.0

OUTPUT

Invalid input

Example 4

INPUT

6
4 2 2 8 3 3 1

OUTPUT

2 2 3 3 4 8

main.kt