Soldiers Row
Soldiers Row
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 ≤ n ≤ 10^5). Second line contains the heights of n soldiers.
Output data
Print n numbers. i-th number 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.
Examples
10 5 3 3 4 9 2 7 5 2 4
-1 0 0 0 -1 4 4 6 7 7