832. The Discount Each Item Gets
A shop lists n items in a fixed order with prices p[0] ... p[n-1].
The rule for item i is: find the FIRST item after it whose price is less than or equal to
p[i], and take that price off as a discount. If no later item is cheap enough, item i pays
full price.
Print the n prices actually paid, in the original order, separated by single spaces.
8 4 6 2 -> 4 2 4 2
1 2 3 4 5 -> 1 2 3 4 5
7 7 7 7 -> 0 0 0 7
In the first row, item 0 costs 8 and the first later price not above 8 is the 4, so it pays 4. Item 1 costs 4 and the first later price not above 4 is the 2, so it pays 2. Item 3 finds nothing after it and pays 2 in full.
Note the third row. Equal counts as "less than or equal", so three of the four sevens are completely free.
## Why scanning forward from each item is too slow
The obvious program walks right from every item until it meets a cheap enough one. On 100000
items priced 100000, 99999, 99998, ... every item finds its discount immediately, which is fast.
Reverse the row to 1, 2, 3, ..., 100000 and every item scans to the end without success, which
is 5 * 10^9 comparisons.
## The stack, and why it decreases
Walk left to right. An item whose answer is not known yet goes on the stack and waits. When
p[i] arrives, every waiting item priced at or above p[i] has just been answered, so it is
popped and paid off.
That leaves the stack holding prices in STRICTLY INCREASING order from the bottom to the top. It has to be: if a lower item were cheaper than the one above it, the cheaper one would have popped it on the way in.
Increasing is the right direction because the question is "what comes next that is SMALL". A decreasing stack would answer "what comes next that is BIG", which is the other problem entirely.
## What is left at the end
Whatever is still on the stack never found a later item at or below its price. Those items pay in full. Do not forget them; a solution that only writes answers inside the pop loop silently leaves them at zero.
## The comparison that decides the equal case
The pop test is p[top] >= p[i], with the =. Use > instead and an item never takes a
discount from an equal price, so 7 7 7 7 comes out as 7 7 7 7 rather than 0 0 0 7. That
single character is the whole difference between the two readings of the rule.
## Related problems
Problem 155 asks for the next smaller VALUE itself rather than the price after subtracting it, and problem 833 asks how many places away the next larger value is. Same scan, three different things to write down when a pop happens.
## Sizes and widths
Prices reach 10^9 and the answer is one price minus another, so every value stays within 32
bits. No product is ever formed, which is why the constraint can be this large safely.
## Cost
Time O(n), since every index is pushed once and popped at most once. Space O(n).
Constraints - `1 ≤ n ≤ 200000` - `1 ≤ p[i] ≤ 10^9`
Input
The first line contains one integer n.
The second line contains n integers p[0] ... p[n-1].
Output
Print n integers on one line, separated by single spaces: the price actually paid for each item, in the original input order. Print no other words.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.