Who Can See Whom

People stand in a single line, all facing right, with heights given by heights (person 0 is at the left end). Person i can see person j further to the right when everyone standing between them is shorter than both of them. Two people standing next to each other can always see each other.

Write visible_counts(heights) that returns a list where position i is the number of people that person i can see to their right.

Examples

visible_counts([4, 2, 3, 1, 5])  # returns [3, 1, 2, 1, 0]
visible_counts([5, 5, 5])        # returns [1, 1, 0]
visible_counts([1, 2, 3, 4])     # returns [1, 1, 1, 0]

In the first example person 0 (height 4) sees the 2 and the 3, cannot see the 1 because the 3 is in the way, and sees the 5 because everyone in between is shorter than 4.

Constraints

• 0 <= len(heights) <= 100,000
• 1 <= heights[i] <= 100,000
• Checking every pair of people is too slow for the longest lines.

Note

Heights can repeat. Someone exactly as tall as the shorter of two people blocks the view between them.