An online auction records n bids in the order they arrived, each a positive integer amount. For every bid, scan forward (toward later bids) and find the nearest later bid whose amount is strictly greater than the current bid's amount. Report that greater amount, or -1 if no later bid is strictly higher.
Input format
Line 1: an integer n.
Line 2: n space-separated integers, the bid amounts in arrival order.
Output format
n space-separated integers on one line: for each bid (in arrival order), the amount of the nearest later strictly-higher bid, or -1.
Constraints
- 1 <= n <= 100000
- 1 <= bid amount <= 1000000000