Visita a Sydney
El pequeño Lucas ha realizado una visita turística a un pueblo cercano a Sydney, una ciudad de Australia. Da la casualidad de que la disposición de las calles en el pueblo parece terriblemente familiar a la forma de un árbol binario perfecto de orden . Un árbol binario perfecto de orden consta de - nodos dispuestos en niveles (al igual que en la imagen). Cada nodo contiene un edificio etiquetado con un número de casa. Además, todos los edificios excepto los del último nivel tienen un hijo izquierdo y uno derecho (ver la imagen de nuevo).
Lucas visitó todos los edificios del pueblo y anotó el orden exacto de entrada. Ahora quiere describirte cómo es el pueblo, pero no puede recordarlo bien. Por suerte, recuerda la forma en que visitó los edificios:
Al principio, estaba parado frente al único edificio en el primer nivel.
Si el edificio frente al que se encuentra actualmente tiene un hijo izquierdo que aún no ha visitado, se moverá frente al hijo izquierdo.
Si el edificio no tiene un hijo izquierdo o ya lo visitó, ingresará al edificio actual y escribirá el número de su casa en su papel.
Si ya ha visitado el edificio actual y el edificio tiene un hijo derecho, se moverá frente al hijo derecho.
Si ha visitado el edificio actual y su hijo izquierdo y derecho, volverá al padre del edificio actual.
Después de visitar los pueblos de las imágenes de arriba, el papel se vería así: –– para el primer pueblo y –––––– para el segundo pueblo. Escriba un programa para ayudar a Lucas a reconstruir el orden de los números de las casas en cada nivel.
Entrada
La primera línea de entrada contiene el número entero (), el número de niveles del pueblo que acaba de visitar Lucas. La segunda línea de entrada contiene - enteros, la secuencia de números de casas en el papel de Lucas. Los números de las casas serán únicos y del intervalo [, - ].
Salida
La salida debe constar de líneas. La i-ésima línea debe contener la secuencia de números de casas en el i-ésimo nivel del pueblo.
Ejemplo de Entrada
3
1 6 4 3 5 2 7
Ejemplo de Salida
3
6 2
1 4 5 7
Comments