#include<cstdio>
typedef long long LL;
const int N=5e5+5;
const int INF=1e9;
int n,a[N],t;
int cnt[N<<2],mn[N<<2],mnid[N<<2],tag[N<<2];
inline int Read(){
	char ch;
	int f=1;
	while((ch=getchar())<'0'||ch>'9')
		if(ch=='-') f=-1;
	int x=ch^48;
	while((ch=getchar())>='0'&&ch<='9')
		x=(x<<3)+(x<<1)+(ch^48);
	return x*f;
}
inline void print(LL x){
	if(x>=10) print(x/10);
	putchar(x%10+48);
	return ;
}
inline void Print(LL x,char ch='\n'){
	if(x<0){
		putchar('-');
		print(-x);
	}
	else print(x);
	putchar(ch);
	return ;
}
inline void Init(){
	n=Read();
	t=1;
	for(int i=1;i<=n;i++)
		a[i]=Read();
	return ;
}
inline void Update(int u){
	cnt[u]=cnt[u<<1]+cnt[u<<1|1];
	if(mn[u<<1]<mn[u<<1|1]){
		mn[u]=mn[u<<1];
		mnid[u]=mnid[u<<1];
	} 
	else{
		mn[u]=mn[u<<1|1];
		mnid[u]=mnid[u<<1|1];
	}
	return ;
}
inline void Build(int u,int ll,int rr){
	cnt[u]=0;
	mn[u]=INF;
	if(ll==rr) return ;
	int mid=ll+rr>>1;
	Build(u<<1,ll,mid);
	Build(u<<1|1,mid+1,rr);
	return ;
}
inline void Add(int u,int val){
	mn[u]+=val;
	tag[u]+=val;
	return ;
}
inline void PushDown(int u){
	if(!tag[u]) return ;
	Add(u<<1,tag[u]);
	Add(u<<1|1,tag[u]);
	tag[u]=0;
	return ;
}
inline void Add(int u,int ll,int rr,int p,int val){
	if(ll==rr){
		cnt[u]=1;
		mn[u]=val;
		mnid[u]=p;
		return ;
	}
	PushDown(u);
	int mid=ll+rr>>1;
	if(mid>=p) Add(u<<1,ll,mid,p,val);
	else Add(u<<1|1,mid+1,rr,p,val);
	return Update(u);
}
inline void Del(int u,int ll,int rr,int p){
	if(ll==rr){
		cnt[u]=0;
		mn[u]=INF;
		mnid[u]=0;
		return ;
	}
	PushDown(u);
	int mid=ll+rr>>1;
	if(mid>=p) Del(u<<1,ll,mid,p);
	else Del(u<<1|1,mid+1,rr,p);
	return Update(u);
}
LL nowans;
inline void Modify(int u,int ll,int rr,int ql,int qr){
	if(ll>=ql&&rr<=qr){
		nowans+=cnt[u];
		return Add(u,-1);
	}
	PushDown(u);
	int mid=ll+rr>>1;
	if(mid>=ql) Modify(u<<1,ll,mid,ql,qr);
	if(mid<qr) Modify(u<<1|1,mid+1,rr,ql,qr);
	return Update(u);
}
inline int Lowbit(int x){
	return x&(-x);
}
struct BIT{
	int c[N];
	inline void Change(int x){
		for(int i=x;i;i-=Lowbit(i))
			c[i]++;
		return ;
	}
	inline int Query(int x){
		int ss=0;
		for(int i=x;i<=n;i+=Lowbit(i))
			ss+=c[i];
		return ss;
	}
}bit;
LL ans[N];
inline void Solve(){
	Build(1,1,n);
	for(int i=1;i<=n;i++){
		Modify(1,1,n,1,a[i]);
		int cnt=bit.Query(a[i]);
		bit.Change(a[i]);
		Add(1,1,n,a[i],cnt);
		while(!mn[1]) Del(1,1,n,mnid[1]);
		ans[i]=nowans;
	}
	if(!t) return Print(ans[n]);
	for(int i=1;i<=n;i++)
		Print(ans[i]);
	return ;
}
#include<ctime>
int main(){
	//freopen("seq.in","r",stdin);
	//freopen("seq.out","w",stdout);
	//#define LOCAL
	#ifdef LOCAL
	int st=clock();
	#endif
	Init();
	Solve();
	#ifdef LOCAL
	int en=clock();
	printf("cost %d ms\n",en-st);
	#endif
	return 0;
}