Queue (隊列+二分詳解）

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 a i.

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 a i > a j. 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 a i (1 ≤ a i ≤ 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

思路：

重點在于構造年齡單調遞減的序列；

最後一個數肯定為-1；

3比50 45都小，故為-1放入隊列；此時隊裡有 45 3；

從隊列裡找到的第一個比它小的數肯定就是離它最遠的比它小的數（因為比隊尾大的數都不放入）

代碼

時間複雜度為nlogn;

#include<stdio.h>
#include<iostream>
#define max 100005
using namespace std;
int a[max];
typedef struct node{
	int age;
	int id;
}node; 
node s[max];
int main()
{
	int n,i,j,k;
	int top;
	top=1;
	scanf("%d",&n);
	for(i=1;i<=n;i++){   //下标是從1開始 
		scanf("%d",&a[i]);
	}
	s[top]={a[n],n};   //将所有滿意的海象，即值為-1的加入隊列中,構造年齡遞減且都滿意的隊列 
	a[n]=-1;//表示滿意度， 
	for(i=n-1;i>=1;i--){  //推進 
			int l,r,mid;
			l=1;r=top;
			while(l<=r){    //二分查找的目的是尋找第一個比它小（即距離它最遠）的下标，隊列是按年齡遞減的 
				mid=(l+r)/2;
				if(s[mid].age>=a[i])l=mid+1;
				else r=mid-1; 
			} 
			if(l<=top){     //說明隊列中存在比它小的數 
				a[i]=s[l].id-i-1;
			}
			else{           //說明隊列中的數都比它大 
				s[++top].age=a[i];   //加入隊列 
				s[top].id=i;
				a[i]=-1;
			}
	}
	for(i=1;i<=n;i++){
		printf("%d ",a[i]);
	}
}