A row of signal towers stands along a ridge, and heights[i] is the height of tower i (left to right). Each tower sends one message eastward (to the right), and it lands on the first tower to its right that is at least as tall as the sender. If no tower to the right is that tall, the message is lost.
Write messages_received(heights: list[int]) -> list[int] that returns, for each tower, how many messages it receives.
messages_received([3, 1, 2, 5, 4, 5]) # [0, 0, 1, 2, 0, 2]
# tower 0 (3) -> tower 3 (5)
# tower 1 (1) -> tower 2 (2)
# tower 2 (2) -> tower 3 (5)
# tower 3 (5) -> tower 5 (5) equal height counts
# tower 4 (4) -> tower 5 (5)
# tower 5 (5) -> lost
messages_received([4, 4, 4]) # [0, 1, 1]
Constraints: up to 2 * 10^5 towers, heights between 1 and 10^9. Scanning right from every tower is O(n²) on a descending row, too slow for the large test.
Show hint
sweep left to right keeping a stack of towers whose message hasn't landed yet (their heights decrease from bottom to top); when a new tower arrives, pop every waiting tower that is no taller than it, and each one popped is a message the new tower receives.