QuickSort Algorithm Challenge

In this problem, you are required to implement the QuickSort algorithm to sort a list of integers in non-decreasing order. QuickSort is a popular divide-and-conquer algorithm. The process is as follows:

1. Choose a pivot element from the list (typically the first element).
2. Partition the remaining elements into two sublists: one with elements less than the pivot and one with elements greater than or equal to the pivot.
3. Recursively apply the above steps to the sublists.
4. Concatenate the sorted sublist of lesser elements, the pivot, and the sorted sublist of greater elements.

The partitioning condition can be mathematically expressed as: $$a_i < pivot$$ for the left side. Your implementation must use the recursive approach as described.

Note: The input will be read from standard input and the output should be printed to standard output.

inputFormat

The input begins with an integer n representing the number of elements. The following line contains n space-separated integers that need to be sorted.

Example:

5
5 4 3 2 1

outputFormat

Output the sorted list as a sequence of integers in non-decreasing order, separated by spaces.

Example:

1 2 3 4 5

## sample

5
5 4 3 2 1

1 2 3 4 5