A queue issued n tickets in order, numbered by the value printed on each ticket (not necessarily distinct). For every ticket, look backward (toward earlier tickets in the queue) and find the nearest earlier ticket whose printed value is strictly greater than the current ticket's value. Report that value, or -1 if no earlier ticket has a strictly greater value.
Input format
Line 1: an integer n.
Line 2: n space-separated integers, the ticket values in issue order.
Output format
n space-separated integers on one line: for each ticket (in issue order), the value of the nearest earlier strictly-greater ticket, or -1.
Constraints
- 1 ≤ n ≤ 100000
- 1 ≤ ticket value ≤ 1000000000