838. The Width Each Bar Rules
A histogram has n bars of width 1 with heights h[0] ... h[n-1].
For each bar, find the LONGEST contiguous stretch of bars that contains it and whose minimum height is exactly that bar's height, and print how many bars that stretch holds.
Print the n widths on one line, separated by single spaces.
2 1 5 6 2 3 -> 1 6 2 1 4 1
3 3 3 3 -> 4 4 4 4
1 2 3 4 5 -> 5 4 3 2 1
Take the 5 at position 3 of the first row. It can reach right over the 6, since 6 does not
lower the minimum, but not over the 2, and to the left it is stopped immediately by the 1. So
its stretch is 5 6, width 2.
In the second row every bar is the same height, so each of them rules the whole row and they all answer 4. Equal heights never stop the spread.
## What actually stops the spread
A bar stops spreading exactly when it meets something STRICTLY SHORTER, because that would drag
the minimum below its own height. So for bar i
width[i] = nextStrictlySmaller(i) - previousStrictlySmaller(i) - 1
with the missing left boundary treated as -1 and the missing right boundary as n.
This one line is the engine underneath most of the rest of this topic. The largest rectangle in a
histogram is max(h[i] * width[i]), and the counting problems later in this block are all
width[i] split into a left part and a right part.
## Why expanding outward from every bar is too slow
The direct reading expands left and right from each bar until it is stopped. On 3 3 3 ... 3
every bar sweeps the entire row, giving n^2 steps, which at n = 200000 is 4 * 10^10.
## The two stacks, and why they increase
Left to right, keep a stack of positions. Before handling i, pop every position whose height is
GREATER THAN OR EQUAL TO h[i]. Whatever remains on top is previousStrictlySmaller(i), or the
stack is empty and the boundary is -1. Then push i.
Right to left, mirror it for nextStrictlySmaller(i).
Both stacks are kept INCREASING in height from the bottom up, because the question asks for something SMALLER. A decreasing stack answers the greater-element question instead, and produces widths that look plausible and are wrong everywhere.
## The equality trap
Both pop tests use >=, so an equal height is popped, and the boundary that remains is strictly
smaller on BOTH sides. That is what makes equal bars all report the full stretch. If you make one
side strict and the other loose (which is what the COUNTING problems in this block do, for a
different reason), then 3 3 3 3 comes out as 4 3 2 1 instead of 4 4 4 4.
Both conventions are useful. Which one is right depends on whether you are measuring one bar's reach, as here, or partitioning every stretch among its bars, as in problem 847.
## Related problems
Problem 169 uses exactly these widths to find the largest rectangle, and reports a single number instead of the whole list. Problem 836 is the same measurement for the opposite comparison.
## Sizes and widths
Heights reach 10^9 and every answer is a width, at most n. The heights are only ever compared,
never combined, so 32 bits covers the whole computation. Problem 169 multiplies these widths by the
heights and immediately needs 64 bits.
## Cost
Time O(n), two stack passes. Space O(n).
Constraints - `1 ≤ n ≤ 200000` - `-10^9 ≤ h[i] ≤ 10^9`
Input
The first line contains one integer n.
The second line contains n integers h[0] ... h[n-1].
Output
Print n integers on one line, separated by single spaces: for each bar, the number of bars in the longest stretch containing it whose minimum is that bar's height. Print no other words.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.