In-Place Array Sorting

Given an array of integers, rearrange it in-place so that the i-th position of the array contains the i-th smallest element. Essentially, your task is to sort the array in non-decreasing order without using additional memory for another array.

You need to implement a program that reads input from standard input and outputs the sorted array to standard output. The problem tests your ability to manipulate arrays and use in-place algorithms.

Note: The algorithm should not use extra space proportional to the input size.

inputFormat

The first line contains a single integer n, the number of elements in the array.

The second line contains n space-separated integers representing the elements of the array.

outputFormat

Output the sorted array in one line, with each element separated by a single space.

5
3 5 2 1 6

1 2 3 5 6