Quick Sort: In-Place Array Sorting

Given an array of integers, your task is to sort the array using the Quick Sort algorithm. Quick Sort is a divide and conquer algorithm which works by partitioning the array into two subarrays around a pivot, and then recursively sorting the subarrays. In this problem, the pivot is chosen as the last element of the array.

The recurrence relation for Quick Sort can be expressed in LaTeX as: $$T(n)=T(k)+T(n-k-1)+O(n)$$, where \(k\) is the number of elements less than or equal to the pivot.

You need to read the input from stdin and output the sorted array to stdout. Each element in the sorted output should be separated by a single space.

inputFormat

The first line of input contains an integer \(n\) representing the number of elements in the array. The second line contains \(n\) space-separated integers.

Example:

6
10 7 8 9 1 5

outputFormat

Output a single line with the \(n\) sorted integers in ascending order separated by a single space.

Example:

1 5 7 8 9 10

## sample

6
10 7 8 9 1 5

1 5 7 8 9 10