A row of n masts is planted left to right, each with a positive integer height. For every mast, look backward (toward masts planted earlier, to its left) and find the nearest earlier mast whose height is strictly smaller than the current mast's height. Report that mast's height, or -1 if no earlier mast is strictly shorter.
Input format
Line 1: an integer n.
Line 2: n space-separated integers, the mast heights from left to right.
Output format
n space-separated integers on one line: for each mast (left to right), the height of the nearest earlier strictly-shorter mast, or -1.
Constraints
- 1 <= n <= 100000
- 1 <= height <= 1000000000