#include <bits/stdc++.h>
#define int long long
using namespace std;
#define rep(i,l,r) for(int i = (l); i <= (r); ++i)
typedef long long ll;
void fast() {
	ios::sync_with_stdio (0);
	cin.tie (0); cout.tie (0);
}

const int N=600010;
int n, m,A[N<<1],c[N];
void upd(int u,int v){
	for(; u<N;u+=u&-u) c[u]+=v;
}
int qry(int u){
	int ret(0);
	for(; u;u-=u&-u)ret+=c[u];
	return ret;
}
int sum[N*20],ls[N*20],rs[N*20],tot;
void upd(int&p, int o,int v,int l=1,int r=n){
	p=++tot;
	sum[p]=sum[o]+1,ls[p]=ls[o],rs[p]=rs[o];
	if(l==r) return;
	int mid=(l+r)>>1;
	((v<=mid)?upd(ls[p],ls[o],v,l,mid):upd(rs[p],rs[o],v,mid+1,r));
}
int getlft(int p,int v,int l=1,int r=n){
	if(l==r||(!p)) return 0;
	int mid=(l+r)>>1;
	if(v<=mid) return getlft(ls[p],v,l,mid);
	else return sum[ls[p]]+getlft(rs[p],v,mid+1,r);
}
int getrgt(int p,int v,int l=1,int r=n){
	if(l==r||(!p)) return 0;
	int mid=(l+r)>>1;
	if(v<=mid) return sum[rs[p]]+getrgt(ls[p],v,l,mid);
	else return getrgt(rs[p],v,mid+1,r);
}
int root[N<<1];
signed main() {
	cin >> n;
	rep(i,1,n) cin>>A[i],++A[i];
	long long init=0;
	rep(i,1,n){
		init+=i-1-qry(A[i]);
		upd(A[i],1);
		A[n+i]=A[i];
	}
	rep(i,1,2*n) upd(root[i],root[i-1],A[i]);
	rep(cur,n,2*n-1){
		int use=A[cur-n+1];
		cout<<init<<'\n';
		init-=(getlft(root[cur],use)-getlft(root[cur-n+1],use));
		init+=(getrgt(root[cur],use)-getrgt(root[cur-n+1],use));
	}
	return 0;
}


/*
start of cp 3.0BETA
https://codeforces.com/problemset/page/1?tags=1800-1800
extending-Beta-test-with-DS&ALGO:https://codeforces.com/problemset/page/1?tags=combine-tags-by-or%2Cdfs+and+similar%2Cdp%2Cshortest+paths%2C2000-2000
Math-Problem-Practice:https://codeforces.com/problemset?tags=math,1400-1500
DEAD PERSON CODING
*/
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define MOD 1000000007
#define int long long int
#define pii pair<int,int>
#define vi vector<int>
#define vii vector<pii>
#define graph vector<vector<int>>
#define print(s) for(auto it:s) cout<<it<<" "
#define print2(s) for(auto it:s) cout<<it.fi<<" : "<<it.se<<endl
#define uset unordered_set
#define maxheap priority_queue<int>
#define minheap priority_queue<int,vi,greater<int>>
#define ln cout<<'\n'
#define space cout<<" "
#define len(x) x.size()
#define bits(x) _builtin_popcount(x)
void fileio()
{
    #ifndef ONLINE_JUDGE
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    #endif
}
graph g;
const int N=200099;
int dp[N][2],lt[N],ft[N];
int n,mx;
int solve(int i,int j){
    if(i==mx+2)return 0;
    int &res=dp[i][j];
    if(res!=-1)return res;
    res=LLONG_MAX;
    int curr=ft[i-1];
    if(j)curr=lt[i-1];
    int ff=ft[i],ll=lt[i];
    if(ff>curr and ll>curr){
        res=min(res,abs(ll-curr)+solve(i+1,1));
    }
    else if(ff<curr and ll<curr){
        res=min(res,abs(curr-ff)+solve(i+1,0));
    }else{
        res=min(res,abs(ll-curr)+abs(ll-ff)+solve(i+1,0));
        res=min(res,abs(curr-ff)+abs(ll-ff)+solve(i+1,1));
    }
    return res;

}

int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    fileio();
    memset(dp,-1,sizeof(dp));
    memset(ft,0,sizeof(ft));
    memset(lt,0,sizeof(lt));
    map<int,int>p,s,idx;
    cin>>n;
    int ct=1;
    for(int i=0;i<n;i++){
        int pos,c;
        cin>>pos>>c;
        if(!p.count(c)){
            p[c]=pos;
            s[c]=pos;
        }else{
            p[c]=min(p[c],pos);
            s[c]=max(s[c],pos);
        }
    }
    for(auto &it:p){
        idx[it.fi]=ct++;
    }
    mx=ct+1;
    for(auto &it:idx){
        ft[it.se]=p[it.fi];
        lt[it.se]=s[it.fi];
    }
    cout<<solve(1,1);

    return 0;
}

        