835. Counting the People Each Person Can See
n people stand in a line with heights h[0] ... h[n-1], all facing RIGHT.
Person i can see person j (with j > i) when everybody standing strictly between them is
SHORTER than both of them, that is
min(h[i], h[j]) > max(h[i+1], ..., h[j-1])
For each person, print how many people they can see. Print the n counts on one line separated by
single spaces. The last person sees nobody and always answers 0.
10 6 8 5 11 9 -> 3 1 2 1 1 0
5 1 2 3 10 -> 4 1 1 1 0
3 3 3 3 -> 1 1 1 0
Person 1 in the first row is 10 tall and sees the 6, then the 8, then the 11. The 5 is hidden behind the 8 and the 9 is hidden behind the 11, so the count is 3.
## The thing the statement quietly promises
Look right from person i while tracking the tallest person seen so far. The people who are
visible are exactly the RECORD HOLDERS of that running maximum, and the sequence of records is
strictly increasing. Person i sees every record shorter than themselves, and then the FIRST
record that reaches their own height, and then nothing at all, because every later record is even
taller and hides behind that one.
So the count is: how many records are shorter than h[i], plus one if any record reaches
h[i].
## Why a stack holds exactly those records
Scan from RIGHT to LEFT. Maintain a stack whose top is the nearest person to the right and whose entries increase in height going down. That stack is precisely the record list for the suffix.
When person i arrives:
pop every entry strictly shorter than h[i] and count each pop
if the stack is still non-empty, add one for the blocker
push h[i]
Popping the shorter records is correct because from anyone further LEFT, those records are now
hidden behind h[i], which is taller and closer. They are dominated on both counts and never
return, which is the usual argument and the reason this whole scan is linear.
## The trap, and it is a real one
Two people of exactly equal height are a record only once. If the blocker at the top has EXACTLY
height h[i], it is still visible to i (so it counts), but it must be REMOVED before pushing
h[i], because from further left the old copy is hidden behind the new one.
Skip that removal and 4 3 6 1 1 2 1 answers 4 for the 6 instead of 2: the two ones both
survive on the stack and both get counted, though the second one is invisible from anywhere left
of the first. Every solution that assumes distinct heights gets this wrong.
## Related problems
Problem 834 asks only WHETHER anybody blocks the view, which is the same scan keeping just the survivors. Problem 833 asks how far away the first blocker stands.
## Sizes and widths
Heights reach 10^9 and every answer is a count of people, at most n. Only comparisons touch the
heights, so 32 bits is enough for everything except the input values themselves.
## Cost
Time O(n): each height is pushed once and popped at most once, and the extra equal-height
removal is at most one per index. 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: how many people each person can see, in the original left-to-right order. Print no other words.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.