Problema número 379

Creciente por los pelos

Tiempo máximo: 1,000 sMemoria máxima: 4096 KiB
Cabezas crecientes por los pelos

Un vector es creciente por los pelos si, además de ser creciente, la diferencia entre dos posiciones consecutivas es como mucho uno. Por ejemplo, existen cuatro vectores crecientes por los pelos de tamaño tres que empiezan por uno: el 1 1 1, el 1 1 2, el 1 2 2 y el 1 2 3. Observa que el 1 1 1 se considera creciente por los pelos, porque no se fuerza a que sea estrictamente creciente y por tanto el caso sin crecimiento también se admite.

Además de comparar individualmente los elementos del vector, podemos también comparar vectores entre sí. Cuando dos vectores tienen el mismo tamaño, uno es menor que otro si tras una primera parte (quizá vacía) de elementos iguales, tiene un elemento menor que el otro. La lista de vectores de tamaño tres anterior es, según esta definición, creciente. Otro ejemplo de secuencia creciente de vectores crecientes por los pelos es:

Ejemplo de secuencia de vectores crecientes

En esa secuencia, sin embargo, hay "huecos" entre los vectores. Por ejemplo, entre el primero, 1 1 1 1 y el segundo, 1 1 2 2, existe un vector creciente por los pelos que es mayor que el primero pero menor que el segundo.

Para poder generar una secuencia de vectores crecientes por los pelos de un tamaño dado, el primer paso es saber, dado uno de estos vectores, cuál sería el siguiente, de forma que no exista ningún otro que esté entre los dos.

Entrada

La entrada está formada por distintos casos de prueba. Cada uno de ellos ocupa dos líneas. La primera contiene un único número N (1 ≤ N ≤ 100) con el tamaño del vector que viene a continuación. La segunda línea contiene los N enteros de un vector creciente por los pelos. El primer elemento de todos los vectores estará siempre entre 1 y 1.000.

Al último caso de prueba le sigue una línea con un 0.

Salida

Por cada caso de prueba se escribirá una línea con el siguiente vector creciente por los pelos al de la entrada, según la definición de orden entre vectores del mismo tamaño dada anteriormente. Los números irán separados por un único espacio.

Entrada de ejemplo

4
1 1 1 1
3
1 1 1
3
1 2 2
0

Salida de ejemplo

1 1 1 2
1 1 2
1 2 3