Try our new interface for solving problems

Soldiers Row

Soldiers Row

Time limit 1 second
Memory limit 128 MiB

Suppose there is a row of n soldiers, identified by indices between 0 and n − 1. They are all lined up in such a way that each soldier i can see only the soldiers with indices between 0 and i − 1. We say that a soldier has clear visibility if he is at least as tall as all of those in front of him. If he doesn't have clear visibility, it means that at least one of the others in front of him is taller.

We are interested in finding out for each soldier if he has clear visibility, and if not, we want to know which the closest previous soldier is taller than him.

Input data

First line contains number of soldiers n~(1 \le n \le 10^5). Second line contains the heights of n soldiers.

Output data

Print n integers. The i-th integer must contain the number of the closest previous soldier who is taller than the i-th soldier. If i-th soldier has a clear visibility, print -1.


Input example #1
5 3 3 4 9 2 7 5 2 4
Output example #1
-1 0 0 0 -1 4 4 6 7 7 
Author Mykhailo Medvediev