408835: GYM103347 E Globe Line

The historic Globe Theatre in London is the well known venue of many of Shakespeare's work. Due to the limited space in the Globe Theatre and the British national hobby of "queuing", the theatre has a very interesting seating procedure, akin to that of an airplane.

To populate the $$$N$$$ seats of the Globe, each audience member is given a ticket with a single number $$$1...N$$$. As they arrive, they're instructed to queue up, that is, stand in such a way that they are behind all lower tickets and in front of all higher tickets.

To ensure that they join in the correct ordering, the staff have instituted a special rule. As soon as an audience member joins the line, they must declare the ticket held by the person currently in front of them.

Given the order of arrivals, help the staff by determining the expected responses.

A single integer, $$$1 \leq N \leq 10^5$$$, the number of ticketholders.

The next $$$N$$$ lines each contain a ticketholder.

For each ticketholder, the ticketholder in line before them, or $$$-1$$$ if no one comes before them.

5
4
1
3
5
2

-1
-1
1
4
1