#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef long double ld;
typedef double db; 
typedef string str; 

typedef pair<int,int> pi;
typedef pair<ll,ll> pl; 
typedef pair<db,db> pd; 

typedef vector<int> vi; 
typedef vector<ll> vl; 
typedef vector<db> vd; 
typedef vector<str> vs; 
typedef vector<pi> vpi;
typedef vector<pl> vpl; 
typedef vector<pd> vpd; 

#define mp make_pair
#define f first
#define s second
#define sz(x) (int)(x).size()
#define all(x) begin(x), end(x)
#define rall(x) (x).rbegin(), (x).rend() 
#define rsz resize
#define ins insert 
#define ft front() 
#define bk back()
#define pf push_front 
#define pb push_back
#define eb emplace_back 
#define lb lower_bound 
#define ub upper_bound 

#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define F0R(i,a) FOR(i,0,a)
#define ROF(i,a,b) for (int i = (b)-1; i >= (a); --i)
#define R0F(i,a) ROF(i,0,a)
#define trav(a,x) for (auto& a: x)

const int MOD = 1e9+7; // 998244353;
const int MX = 2e5+5; 
const ll INF = 1e18; 
const ld PI = acos((ld)-1);
const int xd[4] = {1,0,-1,0}, yd[4] = {0,1,0,-1}; 
mt19937 rng((uint32_t)chrono::steady_clock::now().time_since_epoch().count()); 

template<class T> bool ckmin(T& a, const T& b) { 
	return b < a ? a = b, 1 : 0; }
template<class T> bool ckmax(T& a, const T& b) { 
	return a < b ? a = b, 1 : 0; } 
constexpr int pct(int x) { return __builtin_popcount(x); } 
constexpr int bits(int x) { return 31-__builtin_clz(x); } // floor(log2(x)) 
ll cdiv(ll a, ll b) { return a/b+((a^b)>0&&a%b); } // divide a by b rounded up
ll fdiv(ll a, ll b) { return a/b-((a^b)<0&&a%b); } // divide a by b rounded down
ll half(ll x) { return fdiv(x,2); }

template<class T, class U> T fstTrue(T lo, T hi, U f) { 
	// note: if (lo+hi)/2 is used instead of half(lo+hi) then this will loop infinitely when lo=hi
	hi ++; assert(lo <= hi); // assuming f is increasing
	while (lo < hi) { // find first index such that f is true 
		T mid = half(lo+hi);
		f(mid) ? hi = mid : lo = mid+1; 
	} 
	return lo;
}
template<class T, class U> T lstTrue(T lo, T hi, U f) {
	lo --; assert(lo <= hi); // assuming f is decreasing
	while (lo < hi) { // find first index such that f is true 
		T mid = half(lo+hi+1);
		f(mid) ? lo = mid : hi = mid-1;
	} 
	return lo;
}
template<class T> void remDup(vector<T>& v) { 
	sort(all(v)); v.erase(unique(all(v)),end(v)); }

// INPUT
template<class A> void re(complex<A>& c);
template<class A, class B> void re(pair<A,B>& p);
template<class A> void re(vector<A>& v);
template<class A, size_t SZ> void re(array<A,SZ>& a);

template<class T> void re(T& x) { cin >> x; }
void re(db& d) { str t; re(t); d = stod(t); }
void re(ld& d) { str t; re(t); d = stold(t); }
template<class H, class... T> void re(H& h, T&... t) { re(h); re(t...); }

template<class A> void re(complex<A>& c) { A a,b; re(a,b); c = {a,b}; }
template<class A, class B> void re(pair<A,B>& p) { re(p.f,p.s); }
template<class A> void re(vector<A>& x) { trav(a,x) re(a); }
template<class A, size_t SZ> void re(array<A,SZ>& x) { trav(a,x) re(a); }

// TO_STRING
#define ts to_string
str ts(char c) { return str(1,c); }
str ts(const char* s) { return (str)s; }
str ts(str s) { return s; }
str ts(bool b) { 
	#ifdef LOCAL
		return b ? "true" : "false"; 
	#else 
		return ts((int)b);
	#endif
}
template<class A> str ts(complex<A> c) { 
	stringstream ss; ss << c; return ss.str(); }
str ts(vector<bool> v) {
	str res = "{"; F0R(i,sz(v)) res += char('0'+v[i]);
	res += "}"; return res; }
template<size_t SZ> str ts(bitset<SZ> b) {
	str res = ""; F0R(i,SZ) res += char('0'+b[i]);
	return res; }
template<class A, class B> str ts(pair<A,B> p);
template<class T> str ts(T v) { // containers with begin(), end()
	#ifdef LOCAL
		bool fst = 1; str res = "{";
		for (const auto& x: v) {
			if (!fst) res += ", ";
			fst = 0; res += ts(x);
		}
		res += "}"; return res;
	#else
		bool fst = 1; str res = "";
		for (const auto& x: v) {
			if (!fst) res += " ";
			fst = 0; res += ts(x);
		}
		return res;

	#endif
}
template<class A, class B> str ts(pair<A,B> p) {
	#ifdef LOCAL
		return "("+ts(p.f)+", "+ts(p.s)+")"; 
	#else
		return ts(p.f)+" "+ts(p.s);
	#endif
}

// OUTPUT
template<class A> void pr(A x) { cout << ts(x); }
template<class H, class... T> void pr(const H& h, const T&... t) { 
	pr(h); pr(t...); }
void ps() { pr("\n"); } // print w/ spaces
template<class H, class... T> void ps(const H& h, const T&... t) { 
	pr(h); if (sizeof...(t)) pr(" "); ps(t...); }

// DEBUG
void DBG() { cerr << "]" << endl; }
template<class H, class... T> void DBG(H h, T... t) {
	cerr << ts(h); if (sizeof...(t)) cerr << ", ";
	DBG(t...); }
#ifdef LOCAL // compile with -DLOCAL, chk -> fake assert
	#define dbg(...) cerr << "Line(" << __LINE__ << ") -> [" << #__VA_ARGS__ << "]: [", DBG(__VA_ARGS__)
	#define chk(...) if (!(__VA_ARGS__)) cerr << "Line(" << __LINE__ << ") -> function(" \
		 << __FUNCTION__  << ") -> CHK FAILED: (" << #__VA_ARGS__ << ")" << "\n", exit(0);
#else
	#define dbg(...) 0
	#define chk(...) 0
#endif

// FILE I/O
void setIn(str s) { freopen(s.c_str(),"r",stdin); }
void setOut(str s) { freopen(s.c_str(),"w",stdout); }
void unsyncIO() { ios_base::sync_with_stdio(0); cin.tie(0); }
void setIO(str s = "") {
	unsyncIO();
	// cin.exceptions(cin.failbit); 
	// throws exception when do smth illegal
	// ex. try to read letter into int
	if (sz(s)) { setIn(s+".in"), setOut(s+".out"); } // for USACO
}


/**
 * Description: Calculates least common ancestor in tree with verts 
 	* $0\ldots N-1$ and root $R$ using binary jumping. 
 * Time: O(N\log N) build, O(\log N) query
 * Memory: O(N\log N)
 * Source: USACO Camp, KACTL
 * Verification: *
 */
 
struct LCA {
	int N; vector<vi> par, adj; vi depth;
	void init(int _N) {  N = _N;
		int d = 1; while ((1<<d) < N) d ++;
		par.assign(d,vi(N)); adj.rsz(N); depth.rsz(N);
	}
	void ae(int x, int y) { adj[x].pb(y), adj[y].pb(x); }
	void gen(int R = 0) { par[0][R] = R; dfs(R); }
	void dfs(int x = 0) {
		FOR(i,1,sz(par)) par[i][x] = par[i-1][par[i-1][x]];
		trav(y,adj[x]) if (y != par[0][x]) 
			depth[y] = depth[par[0][y] = x]+1, dfs(y);
	}
	int jmp(int x, int d) {
		F0R(i,sz(par)) if ((d>>i)&1) x = par[i][x];
		return x; }
	int lca(int x, int y) {
		if (depth[x] < depth[y]) swap(x,y);
		x = jmp(x,depth[x]-depth[y]); if (x == y) return x;
		R0F(i,sz(par)) {
			int X = par[i][x], Y = par[i][y];
			if (X != Y) x = X, y = Y;
		}
		return par[0][x];
	}
	int dist(int x, int y) { // # edges on path
		return depth[x]+depth[y]-2*depth[lca(x,y)]; }
};
 
LCA LC;
 
typedef pi T;
 
const int SZ = 1<<19;
struct LazySeg { 
	const T ID = {MOD,0}; 
	T comb(T l, T r) { 
		return l.f != r.f ? min(l,r) : T{l.f,l.s+r.s}; }
	T seg[2*SZ]; int lazy[2*SZ]; 
	LazySeg() { 
		F0R(i,2*SZ) lazy[i] = 0; 
		F0R(i,SZ) seg[SZ+i] = {0,1};
		ROF(i,1,SZ) seg[i] = comb(seg[2*i],seg[2*i+1]);
	}
	void push(int ind, int L, int R) { /// modify values for current node
		if (L != R) F0R(i,2) lazy[2*ind+i] += lazy[ind]; /// prop to children
		seg[ind].f += lazy[ind]; // dependent on operation
		lazy[ind] = 0; 
	} // recalc values for current node
	void pull(int ind) { seg[ind] = comb(seg[2*ind],seg[2*ind+1]); }
	void build() { ROF(i,1,SZ) pull(i); }
	void upd(int lo,int hi,int inc,int ind=1,int L=0, int R=SZ-1) {
		push(ind,L,R); if (hi < L || R < lo) return;
		if (lo <= L && R <= hi) { 
			lazy[ind] = inc; push(ind,L,R); return; }
		int M = (L+R)/2; upd(lo,hi,inc,2*ind,L,M); 
		upd(lo,hi,inc,2*ind+1,M+1,R); pull(ind);
	}
	pi query(int lo, int hi, int ind = 1, int L = 0, int R = SZ-1) {
		push(ind,L,R); if (hi < L || R < lo) return {MOD,0};
		if (lo <= L && R <= hi) return seg[ind];
		int M = (L+R)/2;
		return comb(query(lo,hi,2*ind,L,M),query(lo,hi,2*ind+1,M+1,R));
	}
};
 
int n;
vi p;
vector<vi> child;
vpi inter, range;
vi typ;
vi loc, rloc;
 
pi operator+(pi a, pi b) { return {min(a.f,b.f),max(a.s,b.s)}; }
int len(pi p) { return p.s-p.f; }
bool adj(int _a, int _b) {
	pi a = range[_a], b = range[_b];
	return a.s+1 == b.f || b.s+1 == a.f; 
}

int N;
int root;

void solve() {
	dbg(p);
	// mx-mn-len >= 0
	LazySeg L;
	vi mn{-1}, mx{-1};
	vi st;
	F0R(i,n) {
		if (i) L.upd(0,i-1,-1);
		dbg("ADDING",i);
		{
			while (mn.bk != -1 && p[mn.bk] > p[i]) {
				int t = mn.bk; mn.pop_back();
				L.upd(mn.bk+1,t,p[t]);
			}
			L.upd(mn.bk+1,i,-p[i]); mn.pb(i); 
		}
		{
			while (mx.bk != -1 && p[mx.bk] < p[i]) {
				int t = mx.bk; mx.pop_back();
				L.upd(mx.bk+1,t,-p[t]);
			}
			L.upd(mx.bk+1,i,p[i]); mx.pb(i);
		}
		int cur = N++; loc.pb(cur);
		inter.pb({i,i}); range.pb({p[i],p[i]}); typ.pb(0); child.eb();
		while (sz(st)) {
			if (adj(st.bk,cur)) {
				if (sz(child[st.bk]) && adj(child[st.bk].bk,cur)) {
					assert(typ[st.bk]); // join node
					inter[st.bk] = inter[st.bk]+inter[cur];
					range[st.bk] = range[st.bk]+range[cur];
					child[st.bk].pb(cur);
					cur = st.bk; st.pop_back();
				} else { // make new join node
					int CUR = N++;
					inter.pb(inter[cur]+inter[st.bk]);
					range.pb(range[cur]+range[st.bk]);
					typ.pb(range[st.bk] < range[cur] ? 1 : 2);
					child.pb({st.bk,cur});
					cur = CUR; st.pop_back();
				}
				continue;
			}
			if (L.query(0,inter[cur].f-1).f != 0) break;
			int CUR = N++;
			inter.pb(inter[cur]); range.pb(range[cur]); typ.pb(0); child.pb({cur});
			do {
				assert(sz(st));
				inter[CUR] = inter[CUR]+inter[st.bk];
				range[CUR] = range[CUR]+range[st.bk];
				child[CUR].pb(st.bk); st.pop_back();
			} while (len(inter.bk) != len(range.bk));
			reverse(all(child[CUR])); cur = CUR;
		}
		st.pb(cur);
	}
	assert(sz(st) == 1);
	root = st.bk;
	dbg(root);
	LC.init(N);
	F0R(i,N) trav(t,child[i]) LC.ae(i,t);
	F0R(i,N) dbg(i,typ[i],inter[i],range[i],child[i]);
	LC.gen(root);
	F0R(i,N) if (typ[i]) {
		if (typ[i] == 1) {
			FOR(j,1,sz(child[i])) assert(range[child[i][j-1]].s+1 == range[child[i][j]].f);
		} else {
			FOR(j,1,sz(child[i])) assert(range[child[i][j-1]].f-1 == range[child[i][j]].s);
		}
	}
	rloc = vi(N,-1);
	// dbg("OOPS",loc);
	F0R(i,n) rloc[loc[i]] = i;
}

vector<array<ll,2>> ans;

bool sing(int x) {
	return rloc[x] != -1;
}

vector<array<pi,2>> ex;

vector<pair<pi,int>> v;

void dfsEx(int x) {
	if (rloc[x] != -1) {
		ex[x][0] = ex[x][1] = v[rloc[x]].f;
		return;
	}
	assert(sz(child[x]));
	F0R(i,sz(child[x])) {
		int c = child[x][i];
		dfsEx(c);
		if (i == 0) ex[x][0] = ex[c][0];
		if (i == sz(child[x])-1) ex[x][1] = ex[c][1];
	}
}

ll dis(pi a, pi b) { return abs(a.f-b.f)+abs(a.s-b.s)-1; }

void dfs(int x) {
	// dbg("DFS",x);
	// if (rloc[x] != -1) dbg("HUH",x,rloc[x],typ[x]);
	int zz = sz(child[x]);
	vi lef(zz), rig(zz);
	{
		int l = 0;
		F0R(i,zz) {
			if (!typ[x] || (i && !sing(child[x][i-1]))) l = i;
			lef[i] = l;
		}
	}
	{
		int r = zz-1;
		R0F(i,zz) {
			if (!typ[x] || (i < zz-1 && !sing(child[x][i+1]))) r = i;
			rig[i] = r;
		}
	}
	vl cum(zz);
	FOR(i,1,zz) cum[i] = cum[i-1]+dis(ex[child[x][i]][0],ex[child[x][i-1]][0]);
	F0R(i,zz) {
		int c = child[x][i];
		int l = lef[i], r = rig[i];
		// int l = i, r = i;
		// if (typ[x]) {
		// 	while (l && sing(child[x][l-1])) l --;
		// 	while (r+1 < sz(child[x]) && sing(child[x][r+1])) r ++;
		// }
		auto getSum = [&](int l, int r) {
			return cum[r]-cum[l];
			// ll ans = 0;
			// FOR(i,l,r) ans += dis(ex[child[x][i]][0],ex[child[x][i+1]][0]);
			// return ans;
		};
		auto endLef = [&](pi p) {
			ll ans = 0;
			if (r > i) {
				ans += dis(p,ex[child[x][i+1]][0]);
				ans += getSum(i+1,r);
				p = ex[child[x][r]][0];
			}
			if (l < i) {
				ans += dis(p,ex[child[x][i-1]][0]);
				ans += getSum(l,i-1);
			}
			return ans;
		};
		auto endRig = [&](pi p) {
			ll ans = 0;
			if (l < i) {
				ans += dis(p,ex[child[x][i-1]][0]);
				ans += getSum(l,i-1);
				p = ex[child[x][l]][0];
			}
			if (i < r) {
				ans += dis(p,ex[child[x][i+1]][0]);
				ans += getSum(i+1,r);
			}
			return ans;
		};
		if (l == 0 && r == sz(child[x])-1) {
			F0R(q,2) {
				ans[c][q] = INF;
				if (i > l) ckmin(ans[c][q],endLef(ex[c][q])+ans[x][0]);
				if (i < r) ckmin(ans[c][q],endRig(ex[c][q])+ans[x][1]);
			}
		} else {
			ans[c][0] = min(endLef(ex[c][0]),endRig(ex[c][0]));
			ans[c][1] = min(endLef(ex[c][1]),endRig(ex[c][1]));
		}
		dfs(c);
	}
}

void go() {
	ans.rsz(N); ex.rsz(N);
	// dbg("GOING");
	dfsEx(root);
	// dbg("DONEEX",ex[root]); exit(0);
	dfs(root);
	F0R(i,N) dbg(i,ex[i],child[i],rloc[i],ans[i]);
}


void genAns() {
	vl ret(n);
	ret.rsz(n);
	F0R(i,n) ret[i] = ans[loc[i]][0];
	vl oops(n);
	F0R(i,n) oops[v[i].s] = i;
	F0R(i,n) ps(ret[oops[i]]);
}


int main() {
	setIO(); re(n);
	v.rsz(n);
	int cnt = 0;
	vi y;
	trav(t,v) {
		re(t.f); t.s = cnt++;
		y.pb(t.f.s);
	}
	remDup(y);
	dbg(y);
	sort(all(v));
	trav(t,v) p.pb(lb(all(y),t.f.s)-begin(y));
	solve();
	go();
	genAns();
	// ps(p);
	// you should actually read the stuff at the bottom
}

/* stuff you should look for
	* int overflow, array bounds
	* special cases (n=1?)
	* do smth instead of nothing and stay organized
	* WRITE STUFF DOWN
*/



Measured memory_bytes: 144256