Matcom Online Grader
Faculty of Mathematics and Computer Science of University of Havana

Odín es uno de los dioses mas reverenciados de la Mitología Nórdica. Se sabe que su sed de sabiduría es interminable y que sacrificaría cualquier cosa por ello. Con el objetivo de obtener sabiduría, se ahorcó a él mismo, se hirió con una lanza e incluso dejó de comer y beber durante nueve días y nueve noches. Más notorio aún, se sacó uno de sus ojos por el derecho a beber en El Pozo de Urd, también conocido como el Pozo del Destino. El pozo está localizado en la raíz de Yggdrasil, el árbol que sostiene los nueve mundos en sus ramas. Como ves, así es como funciona el destino en la Mitología Nórdica. El pozo es el símbolo del pasado, y todos los mundos actuales crecen de él. Si se altera el pasado, uno puede influenciar el presente retroactivamente. Ser capaz de manipular eso, es la base para la magia. En teoría, Odin obtuvo el poder de dar forma al cosmos como él desea completando estos rituales.

Si uno quiere seguir el camino de Odín y ser tan poderoso como él, teóricamente es posible. Solo necesitas seguir su camino. Existen $n$ rituales que deben ser completados y deben hacerse en orden secuencial. Y puedes encontrar la ubicación adecuada para cada ritual en los nueve mundos. Sin embargo, uno debe notar que a diferencia de un dios, las vidas mortales no son particularmente largas. Viajar por los nueve mundos no es tan fácil como uno podría imaginarse. Uno no puede simplemente tomar un vuelo de Midgard a Vanaheimr. El viaje debe ser cuidadosamente planeado para que se haga en la vida de uno. Para el viaje, usted puede comenzar en cualquier ubicación.

Input

Output

Imprima el mínimo número de años que tomará finalizar cada ritual secuencialmente desde el número $0$ hasta el $n - 1$. Si es imposible terminar los rituales en dicho orden, entonces imprima $-1$.

Sample test(s)