El verdadero problema en la carrera de la información

A Petya le gusta mucho una secuencia de n números enteros, donde cada elemento de la secuencia es un número entero del 1 al 10e9. Recientemente, la madre de Petya le regaló una serie de números. Pero a él no le gusta. Decidió reemplazar un número en la secuencia con un número entero, que también debe estar entre 1 y 10e9. No se le permite reemplazarse con números, o no se le permite reemplazarlo en absoluto.

Después del reemplazo, petra organiza esta secuencia en una secuencia no descendente (es decir, una secuencia creciente generalizada). Ahora quiere saber cuál es el número más pequeño en cada posición de la secuencia: después de sustitución y permutación.

Entrada: La primera línea es el número entero n (1?≤?n?≤?10e5). Este número indica cuántos números hay en esta secuencia. La segunda línea contiene n números enteros separados por espacios; esta es la parte de descripción de los datos. Cada elemento de esta matriz es un número entero del 1 al 10e9.

Obtenga n números enteros, separados por espacios: el valor más pequeño posible en cada posición en la secuencia después de la permutación y el reemplazo.

Nota: Escribir no es fácil, solo dame puntos.