Algorithm to find the first person in front of $A$ that is shorter than $A$
There is an $O(n)$ solution for building such array using stack.

Starting with a brute force algorithm, you can traverse the array from right to left and for each element in the array, try all elements to the right of it until finding a smaller number. That would be $O(n^2)$.

To get an $O(n)$ solution, instead of each element having to look at all the elements to the right of it. We would just maintain a list of special elements by noticing that whenever a number at position $x$ sees a larger number to the right of it (at position $y$ where $y$ > $x$), the larger number is of no use anymore.

To prove that, we can assume for contradiction that element at position y was the $b_i$ of some future number. That means that $a_y &lt; a_i$ but since $a_x &lt; a_y &lt; a_i$ and $x$ is between $i$ and $y$, then element $x$ would have been $b_i$ instead. Hence, a contradiction.

The algorithm to get $b_i$ would be to do the same as the brute force, but instead of just searching for a smaller element to the right, we will delete the larger elements that we meet on our way and break as soon as we find a smaller number. Simulating this efficiently can be done using a stack, where each $i$ keeps popping elements while the top of the stack is larger than $a_i$. The top of the stack after the pops will be $b_i$. $a_i$ is then pushed to the stack so that it will be seen by the next elements.

Complexity

The algorithm may still look as an $O(n^2)$ algorithm, but looking at the number of times that an array element is checked, we will find that each element is looked at for a constant number of times, since it is either pushed (once), popped (also once) or selected as $b_i$ (total of n for all a $b_i$). So the sum of operations is $O(n)$ for the algorithm.