Skyline Watch

Hard

2s time · 256MB memory · arrays, stacks

From every rooftop in a row of buildings, a watcher looks to the right and notes the height of the first strictly taller building they can see.

For every building, print the height of the first taller building to its right, or −1 if none exists.

Input

The first line contains one integer n — the number of buildings.

The second line contains n integers h₁ … hₙ — the heights, left to right.

Output

Print n space-separated integers — for each building, the height of the first strictly taller building to its right, or −1.

Constraints

  • 1 ≤ n ≤ 2·10⁴
  • 1 ≤ hᵢ ≤ 10⁷
  • Equal height does not count — the next building must be strictly taller.

Samples

Input 1
6
4 5 2 10 8 12
Output 1
5 10 10 12 12 -1
Input 2
3
7 7 7
Output 2
-1 -1 -1
Sign in (top right) to run or submit.