Ordena un arreglo de \(n\) enteros de menor a mayor.

El objetivo del ejercicio es implementar tu propio algoritmo en \(O(n \log n)\) (merge sort, heap sort o quicksort con pivote aleatorio), sin usar la función de ordenamiento de la biblioteca. Los casos incluyen arreglos ya ordenados, invertidos y con todos los valores iguales, que hacen caer a un quicksort ingenuo.

Entrada

La primera línea tiene \(n\) \((1 \le n \le 2 \cdot 10^5)\). La segunda tiene los \(n\) enteros, cada uno entre \(-5 \cdot 10^4\) y \(5 \cdot 10^4\).

Salida

Los \(n\) enteros ordenados de menor a mayor, separados por espacios.

Ejemplo 1

Entrada

4
5 2 3 1

Salida

1 2 3 5

Ejemplo 2

Entrada

6
5 1 1 2 0 0

Salida

0 0 1 1 2 5