Quick Sort

Sort an integer array in ascending order using the Quick Sort algorithm — pick a pivot, partition the values around it, then sort the parts recursively. The judge checks the final sorted output.

Input Format

The first line contains an integer N. The second line contains N space-separated integers.

Output Format

Print the N integers in ascending order, separated by single spaces, on one line.