Card Dropping
Time limit2sMemory limit1024 MB
Given the technique used for each dropped card in order, reconstruct the initial top-to-bottom ordering of cards 1..N that produces a sorted pile.
- Level
Medium7 of 10
- Topics
- Simulation, Linked list, Implementation, Array
- Solved
- No attempts yet
Problem
Suhyeon is practicing card tricks. She will drop the cards in her hand one at a time to build a pile on the floor. She can use the following three techniques.
- Drop the top card onto the floor.
- Drop the second card from the top onto the floor. This can be used only when there are at least 2 cards.
- Drop the bottom card onto the floor. This can be used only when there are at least 2 cards.
Suhyeon starts with N cards in her hand. The cards are labeled with the integers from 1 to N, with no repeats. After she used a technique N times and dropped every card, she checked the pile and found the cards were labeled 1, 2, …, N from top to bottom!
Surprised, Suhyeon wondered how the cards were arranged at the start. Print the initial state of the cards.
Input
The first line gives N (1 ≤ N ≤ 10^6).
The second line gives a sequence A of length N. If A_i is x, it means the x-th technique was used when dropping the i-th card. Each A_i is one of 1, 2, 3, and A_N is always 1.
Output
Print the initial state of the cards from top to bottom.