Queue (Easy)

A group of \(n\) people with heights \(1,2,3, \ldots, n\) is standing in a queue, with arbitrary order. They can see everyone in front (left) of them, until there is someone taller than them. For clarity, look at queue of 6 people :

The circle represents their height and the number below them indicates the number of people they can see.

Starting from the first person, you ask them the question "How many people can you see standing in front of you?" and note down their response. When you are going to trace back their heights, you noticed that some information is wrong! That is, it's not possible for the person to see that number of people despite the sequence of heights in the queue. Given the responses, find the first (leftmost) information that is wrong.

0 1 0 2 4 0 0 2

If you think that the \(3^\text{rd}\) person from the left is the one who gave wrong information, output your answer as 3. If all information are correct (possible to generate a sequence of heights), output your answer as 0.


Problem Loading...

Note Loading...

Set Loading...