You are given an array of n integers. For each position i, its next greater element is the value of the first element that appears strictly after i and is strictly greater than a[i]. If no such element exists, the answer for that position is -1.
Output the answer for every position, in order.
Input format
Line 1: an integer n.
Line 2: n space-separated integers a[0] a[1] ... a[n-1].
Output format
A single line with n space-separated integers: the next greater element for each position from left to right.
Constraints
- 1 ≤ n ≤ 100000
- -1000000000 ≤ a[i] ≤ 1000000000