The Hints of Ali Baba

One Thousand and One Nights is a collection of Arabic stories that date back to the ninth century. Some translations have been made to the West from the seventeenth century, and some of these stories, such as "Sinbad the Sailor", "Aladdin and the Magic Lamp" and "Ali Baba and the Forty Thieves" are now known to children around the world. In the story of Ali Baba the treasures are stored in a cave that opens when the words "Open Sesame" is used. In fact, the treasure was hidden in a safe in the cave wall, which opened when a permutation of the integers from 1 to N was recited. Not all 40 thieves had good memory, so Ali Baba had to maintain on the walls of the cave, hints on how to reconstruct the permutation, if any of the thieves forget. He wrote down a sequence of integers a₁, a₂, ... , a_k generated from the permutation that opened the safe after possible applications of the following operations: duplication (i, j) and mirroring (i, j), for i ≤ j. The doubling operation (i, j) creates a copy of the subsequence a_i, a_i+1, ... , aj and inserted between aj and a_j+1. The mirroring operation (i, j) inserts an inverted copy of the subsequence ai to a_j (a_j, a_j-1, ..., a_i) between a_j and a_j+1.

For exemple, given the sequence (a₁, a₂, a₃, a₄, a₅, a₆), the aplication of the mirroring operation (3,5) generates the sequence (a₁, a₂, a₃, a₄, a₅, a'₅, a'₄, a'₃, a₆).

Your task is recontruct the original permutation.