Quick Sort

Mediumjavapythonccppjavascript

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.

Example 1

Input

6
10 7 8 9 1 5

Output

1 5 7 8 9 10

Explanation: Values are partitioned around a pivot and each part sorted recursively.

Input (stdin)

Output

Run your code to see output here...