Signal Towers Along the Ridge

Signal towers stand in a straight line along a ridge; heights[i] is the height of tower i. Two towers i < j can flash signals to each other when no tower strictly between them is taller than the shorter of the two, that is, every tower between them has height at most min(heights[i], heights[j]). Neighbouring towers can always signal each other.

Return the number of pairs of towers that can signal each other. Return 0 for fewer than two towers.

Examples

Input:  heights = [4, 2, 3, 1, 3]
Output: 7
Explanation: the 4 neighbouring pairs, plus towers (0,2), (0,4) and (2,4).
Tower 1 and tower 4 cannot: the 3 between them is taller than 2.

Input:  heights = [2, 2, 2]
Output: 3
Explanation: equal towers do not block each other, so every pair works.

Input:  heights = [1, 5, 1]
Output: 2

Constraints

• 0 <= len(heights) <= 2 * 10**5
• 1 <= heights[i] <= 10**9
• Target: O(n) time

Goals

• Count visible pairs without examining every pair
• Keep a monotonic stack of heights together with how many equal towers each entry stands for
• Treat equal heights carefully: they do not block each other