ZCMU--2192: Queue

Description

There are n walruses standing in a queue in an airport. They are numbered starting from the queue's tail: the 1-st walrus stands at the end of the queue and the n-th walrus stands at the beginning of the queue. The i-th walrus has the age equal to ai.

The i-th walrus becomes displeased if there's a younger walrus standing in front of him, that is, if exists such j (i<j), that ai>aj. The displeasure of the i-th walrus is equal to the number of walruses between him and the furthest walrus ahead of him, which is younger than the i-th one. That is, the further that young walrus stands from him, the stronger the displeasure is.

The airport manager asked you to count for each of n walruses in the queue his displeasure.

Input

The first line contains an integer n (2≤n≤105) − the number of walruses in the queue. The second line contains integers ai (1≤ai≤109).

Note that some walruses can have the same age but for the displeasure to emerge the walrus that is closer to the head of the queue needs to be strictly younger than the other one.

Output

Print n numbers: if the i-th walrus is pleased with everything, print "-1" (without the quotes). Otherwise, print the i-th walrus's displeasure: the number of other walruses that stand between him and the furthest from him younger walrus.

Examples

Input

6
10 8 5 3 50 45

Output

2 1 0 -1 0 -1 

Input

7
10 4 6 3 2 8 15

Output

4 2 1 0 -1 -1 -1 

Input

5
10 3 1 10 11

Output

1 0 -1 -1 -1 

解析：我们可以用单调栈思想来解决，开一个b[ ]从末尾开始往前记录单调递减的元素，因为如果对于Ak，右边有两个元素 Ai，Aj( i < j ，Ai>Aj)，那么Ai其实没有必要存储在b[ ]，因此b数组就存储了从末尾开始往前记录单调递减的元素。

遍历的时候我们记录一个最小值minn，如果Ai等于minn，那么它将输出-1，如果小于minn，它将输出-1，并且将Ai加入到b数组中，如果大于minn，那么我们就二分找到b数组中第一个小于它的元素，因为我们倒着存入b中，所以找到的就是最右边小于它的。

因为要算两者之间的距离，我们可以开个map来记录每个元素最右边的下标。

#include <stdio.h>
#include <map>
using namespace std;
const int N=100005;
int a[N],b[N];//a记录原始数据且最后更新为答案数组，b记录从后往前单调递减元素
map<int,int> mp;
int main()
{
    int n,minn=0x3f3f3f3f,cnt=0;//将minn设置为最大值
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]),mp[a[i]]=i;
    for(int i=n;i>=1;i--)
    {
        if(a[i]==minn) a[i]=-1;//等于minn
        else if(a[i]<minn) minn=a[i],b[++cnt]=a[i],a[i]=-1;//小于minn，并将a[i]加入b中
        else{//大于minn
            int l=1,r=cnt;
            while(l<=r)
            {
                int m=(l+r)>>1;
                if(b[m]>=a[i]) l=m+1;
                else r=m-1;
            }
            a[i]=mp[b[l]]-i-1;
        }
    }
    for(int i=1;i<=n;i++)
    {
        if(i!=1) printf(" ");
        printf("%d",a[i]);
    }
    return 0;
}