#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN=500005;
ll res[MAXN];
int n,a[MAXN],b[MAXN],pos[MAXN],t[MAXN];
inline void add(int x,int y) {
	for(; x<=n; x+=x&-x) t[x]+=y;
}
inline int query(int x) {
	int sum=0;
	for(; x; x&=x-1) sum+=t[x];
	return sum;
}
struct Tree {
	int l,r,lt,cnt,mx;
	ll sum;
} tr[MAXN<<2];
void build(int num,int l,int r) {
	tr[num].l=l,tr[num].r=r,tr[num].sum=tr[num].cnt=tr[num].lt=0;
	tr[num].mx=-1e9;
	if(l==r)return ;
	build(num<<1,l,l+r>>1),build(num<<1|1,l+r+2>>1,r);
}
inline void push_up(int num) {
	tr[num].sum=tr[num<<1].sum+tr[num<<1|1].sum;
	tr[num].cnt=tr[num<<1].cnt+tr[num<<1|1].cnt;
	tr[num].mx=max(tr[num<<1].mx,tr[num<<1|1].mx);
}
inline void Tag(int num,ll x) {
	if(!tr[num].cnt)return;
	tr[num].sum+=tr[num].cnt*x;
	tr[num].lt+=x,tr[num].mx+=x;
}
inline void push_down(int num) {
	if(tr[num].lt) {
		Tag(num<<1,tr[num].lt),Tag(num<<1|1,tr[num].lt);
		tr[num].lt=0;
	}
}
void updatel(int num,int x,int l) {
	if(tr[num].l==tr[num].r) {
		if(l>0) tr[num].sum=tr[num].mx=-l,tr[num].cnt=1;
		else tr[num].sum=0,tr[num].mx=-1e9,tr[num].cnt=0;
		return;
	}
	push_down(num);
	updatel(num<<1|(x>tr[num<<1].r),x,l);
	push_up(num);
}
void chk(int num) {
	if(tr[num].mx<0) return;
	if(tr[num].l==tr[num].r) {
		tr[num].cnt=0,tr[num].mx=-1e9;
		return;
	}
	push_down(num);
	if(!tr[num<<1  ].mx)chk(num<<1  );
	if(!tr[num<<1|1].mx)chk(num<<1|1);
	return push_up(num);
}
void update(int num,int l,int r,ll x) {
	if(l<=tr[num].l&&tr[num].r<=r)return Tag(num,x),chk(num);
	push_down(num);
	if(l<=tr[num<<1].r) update(num<<1,l,r,x);
	if(tr[num<<1].r<r)  update(num<<1|1,l,r,x);
	return push_up(num);
}
inline void solve() {
	for(int i=1; i<=n; ++i) a[i]=n-a[i]+1,pos[a[i]]=i,t[i]=0;
	build(1,1,n);
	ll ans=0;
	for(int i=1,L=0; i<=n; ++i) {
		L=query(a[i]),ans+=L;
		updatel(1,a[i],L);
		if(a[i]<n)update(1,a[i]+1,n,1);
		add(a[i],1);
		res[i]=min(res[i],ans+tr[1].sum);
	}
}
int main() {
	scanf("%d",&n);
	for(int i=1; i<=n; ++i) scanf("%d",&a[i]),b[i]=a[i],res[i]=1e18;
	sort(b+1,b+n+1);
	for(int i=1; i<=n; ++i) a[i]=lower_bound(b+1,b+n+1,a[i])-b;
	solve(),solve();
	for(int i=1; i<=n; ++i) printf("%lld\n",res[i]);
	return 0;
}