Queue

Time limit 2000 ms Memory limit 262144 kB

数据结构

知识点：线段树的查询，更新

来源：
codeforces：codeforces 91 B Queue
vjudge： F-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 

题意：

 有n只海象，入过有比它年纪小的排在它的前面他就不高兴，越前面越不高兴，他们中间隔了多少只海象它的不高兴的值就为多少，如果他的前面没有比它年纪小的海象，则输出-1；
输入第一行输入一个n，表示有n只海象
接下来输入一个序列a[n]，表示海象的年纪，他们排序是从右往左排的，右为头，左为尾。

解题思路

线段树维护区间最小值，循环一遍数组，每次找到比这个数小且在最右端的数，将左边处理过的数更新为INF，更新最小值。查询之前，先将整个数组的最小值与当前值比较，若最小值<当前值则查询，且若右边不成立则查询左边。

完整代码：

#include<stdio.h>
#include<string.h>
#include<algorithm>
#define inf 0x3f3f3f3f
///至今不清楚0x3ffffff与0x3f3f3f3f的区别，总之用0x3ffffff是要错的！！唉，，记住吧，百度一下，貌似0x3f3f3f3f比较好一点，那以后就用它吧！
using namespace std;
int p[100010];
int ans[100010];
struct node
{
    int l,r,n;
}tree[100010*4];
void build(int id,int l,int r)
{
    int mid;
    tree[id].l=l;
    tree[id].r=r;
    mid=(l+r)/2;
    if(l==r)
     {
        tree[id].n=p[mid];
        return;
     }
     build(2*id,l,mid);
     build(2*id+1,mid+1,r);
    tree[id].n=min(tree[2*id].n,tree[2*id+1].n);
}
int query(int id,int a,int b,int i)///查询
{
    int mid;
    if(tree[id].l==tree[id].r)
        return tree[id].l-i-1;///它的不高兴值
    mid=(tree[id].l+tree[id].r)/2;
    if(p[i]<=tree[2*id+1].n)
         return query(2*id,a,mid,i);
    else
        return query(2*id+1,mid+1,b,i);
}
void update(int id,int pos)///更新
{
    int mid;
    mid=(tree[id].l+tree[id].r)/2;
    if(tree[id].l==tree[id].r)
    {
        tree[id].n=inf;///该为inf
        return;
    }
    if(pos<=mid)//x在左
        update(2*id,pos);
    else
        update(2*id+1,pos);//x在右
   tree[id].n=min(tree[2*id].n,tree[2*id+1].n);
}
int main()
{
    int n;
    while(scanf("%d",&n)!=EOF)
    {
        memset(ans,0,sizeof(ans));
        memset(p,0,sizeof(p));
        for(int i=1;i<=n;i++)
            scanf("%d",&p[i]);
        build(1,1,n);
        for(int i=1;i<=n;i++)
        {
            if(tree[1].n>=p[i])
                ans[i]=-1;
            else
                ans[i]=query(1,1,n,i);
            update(1,i);
        }
        for(int i=1;i<=n;i++)
        {
            if(i==1)
                printf("%d",ans[i]);
            else
                printf(" %d",ans[i]);
        }
        printf("\n");
    }
    return 0;
}