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 determining, for each soldier, whether he has clear visibility. If not, we want to identify the closest previous soldier who is taller than him.
The first line contains the number of soldiers n (1≤n≤105). The second line contains the heights of n soldiers.
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 the i-th soldier has clear visibility, print −1.