837. Next Bigger Around a Ring
n values are arranged in a CIRCLE, so the element after a[n-1] is a[0] again.
For each element, walk forward around the circle and print the first strictly larger value you
meet. You may go all the way around, but you stop before returning to your own position, so an
element is never its own answer. Print -1 when the circle contains nothing larger.
Print the n answers on one line, separated by single spaces.
1 2 1 -> 2 -1 2
1 2 3 4 -> 2 3 4 -1
5 4 3 2 -> -1 5 5 5
In the first row the last 1 finds nothing to its right, wraps to the front, passes the 1, and
meets the 2. Only the overall maximum can ever answer -1, and every copy of the maximum
answers -1.
## Why the straight-line scan is not enough, and why doubling the array is
On a straight line, an element with nothing larger to its right is finished. On a circle it is not: the answer may sit anywhere in the prefix it has not looked at yet.
The fix is to run the same left-to-right stack scan over TWO copies of the array laid end to end,
a total of 2n steps, while pushing only the first n positions. Every position then gets a
full lap of lookahead, which is all the circle can offer, and nothing is pushed twice.
Actually copying the array is unnecessary. Loop p from 0 to 2n - 1 and use i = p % n
as the index; the second lap answers leftovers without creating new ones.
## The stack, and why it decreases
The stack holds positions still waiting for an answer. When a[i] arrives, pop every waiting
position whose value is strictly smaller and record a[i] as its answer. Kept this way the stack
runs in non-increasing value order from the bottom up, which is the shape that answers "what is
the next BIGGER value".
The domination argument is unchanged by the wrap: once a waiting position has been answered it is
gone, so across the whole 2n sweep there are at most n pushes and n pops.
## What is left at the end
Anything still on the stack after two laps has looked at every other element and found nothing
strictly larger. Those are the copies of the maximum, and they answer -1. Fill the answer array
with -1 before the scan and they are handled.
## The two traps
First, push only while p < n. Push on the second lap as well and positions get answered twice,
or worse, get answered by themselves.
Second, pop on a[top] < a[i], strictly, since equal is not larger. 3 3 3 3 3 must answer all
-1; with <= every element would answer 3.
## Related problems
Problem 154 is this question on a straight line, reported as a value, with no wrap at all. The whole difference here is the second lap, and recognising that a second lap is enough.
## Sizes and widths
Values reach 10^9 and the answers ARE input values, so the output range is the input range.
Nothing is summed, so 32 bits is enough.
## Cost
Time O(n): 2n iterations, n pushes, at most n pops. Space O(n).
Constraints - `1 ≤ n ≤ 200000` - `-10^9 ≤ a[i] ≤ 10^9`
Input
The first line contains one integer n.
The second line contains n integers a[0] ... a[n-1], given in circular order.
Output
Print n integers on one line, separated by single spaces: for each element, the first strictly larger value found walking forward around the circle, or -1 if there is none. Print no other words.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.