#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define MOD int(1e9+7)
#define INF int(1e9+7)
#define LINF ll(1e18+7)
#define PI acos(-1)
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define P pair<ll,ll>
#define chmax(x,y) (x = max(x,y))
#define chmin(x,y) (x = min(x,y))

int n;
ll a[310000];

const int SEG_LEN=1<<19;
int seg[SEG_LEN*2];

void update(int ind, int val){
  ind += SEG_LEN;
  seg[ind]=val;
  while(ind!=0){
    ind/=2;
    seg[ind]=seg[ind*2]+seg[ind*2+1];
  }
  return;
}

int getsum(int ql, int qr, int sl=0, int sr=SEG_LEN, int pos=1){
  if(qr<=sl || sr<=ql) return 0;
  if(ql<=sl && sr<=qr) return seg[pos];
  int sm=(sl+sr)/2;
  return getsum(ql,qr,sl,sm,pos*2)+getsum(ql,qr,sm,sr,pos*2+1);
}

int main(){
  cin>>n;
  rep(i,n) cin>>a[i];
  ll inv=0;
  rep(i,n){
    update(a[i],1);
    inv += getsum(a[i]+1,n);
  }
  cout<<inv<<endl;
  rep(i,n-1){
    inv=inv-a[i]+n-a[i]-1;
    cout<<inv<<endl;
  }
}
#include<bits/stdc++.h>
typedef unsigned long long ull;
typedef long long ll;
#define rep(i,l,r) for(int i=l;i<=r;i++)
#define nep(i,r,l) for(int i=r;i>=l;i--)
void sc(int &x){scanf("%d",&x);}
void sc(int &x,int &y){scanf("%d%d",&x,&y);}
void sc(int &x,int &y,int &z){scanf("%d%d%d",&x,&y,&z);}
void sc(ll &x){scanf("%lld",&x);}
void sc(ll &x,ll &y){scanf("%lld%lld",&x,&y);}
void sc(ll &x,ll &y,ll &z){scanf("%lld%lld%lld",&x,&y,&z);}
void sc(char *x){scanf("%s",x);}
void sc(char *x,char *y){scanf("%s%s",x,y);}
void sc(char *x,char *y,char *z){scanf("%s%s%s",x,y,z);}
void out(int x){printf("%d\n",x);}
void out(ll x){printf("%lld\n",x);}
void out(int x,int y){printf("%d %d\n",x,y);}
void out(ll x,ll y){printf("%lld %lld\n",x,y);}
void out(int x,int y,int z){printf("%d %d %d\n",x,y,z);}
void out(ll x,ll y,ll z){printf("%lld %lld %lld\n",x,y,z);}
using namespace std;
const int N=3e5+5;
struct node
{
    int x,y,id;
}a[N];
int n;
bool cmp1(node &x,node &y)
{
    return x.x<y.x;
}
bool cmp2(node &x,node &y)
{
    return x.y<y.y;
}
map<pair<int,int>,bool>vis;
vector<int>v;
void add(int x,int y)
{
    if(vis[{a[x].id,a[y].id}]) return;
    vis[{a[x].id,a[y].id}]=vis[{a[y].id,a[x].id}]=true;
    v.push_back(max(abs(a[x].x-a[y].x),abs(a[x].y-a[y].y)));
}
int main()
{
    //freopen("1.in","r",stdin);freopen("1.out","w",stdout);
    sc(n);
    rep(i,1,n) sc(a[i].x,a[i].y),a[i].id=i;
    sort(a+1,a+1+n,cmp1);
    add(1,n);
    add(1,n-1);
    add(2,n);
    sort(a+1,a+1+n,cmp2);
    add(1,n);
    add(1,n-1);
    add(2,n);
    sort(v.begin(),v.end());
    reverse(v.begin(),v.end());
    out(v[1]);
}
