#include<bits/stdc++.h>
#define int long long
using namespace std;
int n;
int a[200005];
int an[200005];
int bn[200005];
int ls[200005];
struct P{int l,r,sum,minn,num,tag;}tree[800005];
void build(int t,int l,int r){
tree[t].l=l,tree[t].r=r;
if(l==r)return ;
int mid=l+r>>1;
build(2*t,l,mid);
build(2*t+1,mid+1,r);
return ;
}
void pushdown(int t){
tree[2*t].minn-=tree[t].tag;
tree[2*t+1].minn-=tree[t].tag;
tree[2*t].tag+=tree[t].tag;
tree[2*t+1].tag+=tree[t].tag;
tree[t].tag=0;
return ;
}
int check(int t,int ll,int rr){
int l=tree[t].l,r=tree[t].r;
if(ll<=l and r<=rr)return tree[t].sum;
pushdown(t);
int mid=l+r>>1;
int ans=0;
if(ll<=mid)ans=check(2*t,ll,rr);
if(rr>mid)ans+=check(2*t+1,ll,rr);
return ans;
}
int cnum(int t,int ll,int rr){
int l=tree[t].l,r=tree[t].r;
if(ll<=l and r<=rr)return tree[t].num;
pushdown(t);
int mid=l+r>>1;
int ans=0;
if(ll<=mid)ans=cnum(2*t,ll,rr);
if(rr>mid)ans+=cnum(2*t+1,ll,rr);
return ans;
}
void mk(int t,int x,int c){
int l=tree[t].l,r=tree[t].r;
if(l==r){
if(c)tree[t].minn=c;
else tree[t].minn=1e9;
if(c)tree[t].sum=1;
tree[t].num=1;
return ;
}
pushdown(t);
int mid=l+r>>1;
if(x<=mid)mk(2*t,x,c);
else mk(2*t+1,x,c);
tree[t].minn=min(tree[2*t].minn,tree[2*t+1].minn);
tree[t].sum=tree[2*t].sum+tree[2*t+1].sum;
tree[t].num=tree[2*t].num+tree[2*t+1].num;
return;
}
void change(int t,int ll,int rr){
if(ll>rr)return ;
int l=tree[t].l,r=tree[t].r;
// cerr<<l<<' '<<r<<' '<<tree[t].minn<<'\n';
if(ll<=l and r<=rr)--tree[t].minn;
if(tree[t].minn>1){++tree[t].tag;return ;}
if(l==r){
tree[t].minn=1e9;
tree[t].sum=0;
// cerr<<'d'<<l<<' ';
tree[t].num=1;
return ;
}
pushdown(t);
int mid=l+r>>1;
if(ll<=mid)change(2*t,ll,rr);
if(rr>mid)change(2*t+1,ll,rr);
tree[t].minn=min(tree[2*t].minn,tree[2*t+1].minn);
tree[t].sum=tree[2*t].sum+tree[2*t+1].sum;
tree[t].num=tree[2*t].num+tree[2*t+1].num;
return ;
}
void omt(){
for(int i=1;i<=800000;++i)tree[i]={0,0,0,1e9,0,0};
build(1,1,n);
for(int i=1;i<=n;++i){
an[i]=an[i-1]+check(1,1,a[i]);
mk(1,a[i],cnum(1,a[i]+1,n));
change(1,1,a[i]-1);
}
return ;
}
void ogl(){
for(int i=1;i<=800000;++i)tree[i]={0,0,0,1e9,0,0};
build(1,1,n);
for(int i=1;i<=n;++i){
bn[i]=bn[i-1]+check(1,a[i],n);
// cerr<<'a'<<cnum(1,1,a[i])<<' ';
mk(1,a[i],cnum(1,1,a[i]));
change(1,a[i]+1,n);
}
return ;
}
signed main(){
cin.tie(0)->sync_with_stdio(0);
//freopen("1.in","r",stdin);
cin>>n;
for(int i=1;i<=n;++i)cin>>a[i];
for(int i=1;i<=n;++i)ls[i]=a[i];
sort(ls+1,ls+n+1);
for(int i=1;i<=n;++i)a[i]=lower_bound(ls+1,ls+n+1,a[i])-ls;
omt();ogl();
// for(int i=1;i<=n;++i)cerr<<an[i]<<' ';
// cerr<<'\n';
// for(int i=1;i<=n;++i)cerr<<bn[i]<<' ';
for(int i=1;i<=n;++i)cout<<min(an[i],bn[i])<<'\n';
return 0;
}