# Holes (Hard)

One fateful day, 9 people numbered 1, 2, 3, 4, 5, 6, 7, 8 and 9 are trying to cross a road that contains several deep holes. To pass through a hole with depth 3, the 3 leading people have to go into the holes in order so that the other people can safely cross the hole. Then, the last people who crossed the hole will pull the highest people from the hole up, and so on. For clarity, look at the diagram below where 4 people is crossing a hole with depth 3 :

If the output sequence is $$1,2,3,4,5,6,7,8,9$$ and the $$30$$ holes they must pass through in order has depth of

 1 3 5 9 8 5 1 8 5 4 5 3 8 6 7 2 6 3 9 2 5 2 7 8 6 7 3 6 9 2 5 

respectively, what is the input sequence?

If you think the output sequence is $$6,5,4,3,2,1$$, input your answer as 654321.

You are advised to solve the Easy and Medium version of this problem first.

×