Next Greater Element in a Cyclic Array
Given a cyclic array nums of length n, for each element nums[i], find the first element nums[j] that is greater than nums[i] in the cyclic order. If no such element exists, output -1 for that element.
A cyclic array means that the element after nums[n-1] is nums[0].
For example, if nums = [1, 2, 1], the cyclic array is [1, 2, 1, 1, 2, 1, 1, 2, 1, ...]. The next greater element for the first 1 is 2. The next greater element for 2 is -1. The next greater element for the second 1 is -1.
Input
The first line contains an integer n (1 <= n <= 200000).
The second line contains n integers nums[0], nums[1], ..., nums[n-1] (-10^9 <= nums[i] <= 10^9).
Output
Print n integers, where the i-th integer is the next greater element for nums[i]. If no greater element exists, print -1.
Constraints
1 <= n <= 200000 -10^9 <= nums[i] <= 10^9
Example 1
3 1 2 1
2 -1 2
For 1, the next greater is 2. For 2, there's no greater element in cyclic order. For the second 1, there's no greater element.
Example 2
5 1 3 2 4 5
3 4 4 5 -1
The next greater elements are 3, 4, 4, 5, -1 respectively.
Hints
# Read the input from stdin and print the answer.
import sys
def main():
data = sys.stdin.read().split()
# your code here
main()
3 1 2 1
5 1 3 2 4 5