Il était une fois un enfant appelé Kino qui aimait beaucoup voyager et avait visité de nombreux endroits étranges. Un jour, il arriva près d'un grand pont et y découvrit de nombreuses voitures décapotables à l'arrêt. Malheureusement, le pont était si étroit qu'une seule décapotable pouvait passer de front. Comme les voitures sur le pont refusaient de se céder le passage, celles venant des deux directions étaient bloquées.
Par la suite, le constructeur ajouta une nouvelle fonction au pont : une de ses sections pouvait pivoter de $180$ degrés, retournant ainsi les décapotables de cette section, comme le montre la figure ci-dessous :
Figure 1. Après rotation, les décapotables 321 deviennent 123.
Comme le montre la figure, la rencontre des décapotables $321$ et $45$ sur le pont provoque un embouteillage. On peut alors faire pivoter la section contenant $321$ : l'ordre des décapotables devient $12345$, et elles sont toutes orientées dans la même direction, ce qui leur permet de quitter le pont. Bien entendu, il ne s'agit que d'un exemple simple : en réalité, la situation sur le pont est bien plus compliquée et plusieurs rotations sont nécessaires pour obtenir la forme $12345$.
Mais, après avoir conçu le pont, son concepteur partit lui aussi en voyage. Aucun des habitants restants ne savait utiliser ce pont magique. La situation devint donc de plus en plus chaotique, jusqu'à aboutir un jour à l'état actuel. Pour traverser, Kino trouva près du pont son dispositif de commande et son manuel, puis redécouvrit comment le faire fonctionner. Avec l'aide des habitants des environs, il parvint à ranger les décapotables dans l'ordre $1,2,3,\ldots$, toutes orientées dans la même direction. Savez-vous comment il s'y est pris ?
Entrée
Il s'agit d'un problème où seules les réponses doivent être soumises. Les fichiers d'entrée convertible1.in à convertible10.in sont déjà placés dans le répertoire utilisateur. La première ligne de chaque fichier contient le nombre $n$ de décapotables sur le pont, numérotées $1,2,\ldots,n$. La deuxième ligne décrit leur position et leur orientation par une suite de valeurs $+i$ ou $-i$. Une valeur $-i$ en position $j$ indique que la décapotable $i$ occupe la position $j$ du pont et est orientée vers la droite ; une valeur $+i$ en position $j$ indique que la décapotable $i$ y est orientée vers la gauche.
Sortie
Vous devez placer les fichiers de sortie convertible1.out à convertible10.out dans le répertoire utilisateur, sans soumettre de programme. La première ligne de chaque fichier contient le nombre $m$ de rotations. Chacune des $m$ lignes suivantes décrit une rotation par les positions de ses bornes gauche et droite. Votre sortie doit garantir que la suite finale est $1,2,3,\ldots,n$, et non $-1,-2,-3,\ldots,-n$ ou une autre suite.
Exemples
Entrée 1
5 -3 -2 -1 4 5
Sortie 1
1 1 3
Sous-tâches
Chaque test vaut au maximum 10 points. Le score dépend du rapport entre la qualité de votre résultat et celle de la réponse de référence.
Comment tester votre programme
Un vérificateur des données de sortie, convertible_c, est fourni. Il s'utilise ainsi :
#./convertible_c 3
Cette commande vérifie si convertible3.out est valide.