# include <bits/stdc++.h>

using namespace std;

const int N = 2e5 + 5;
int n , a[N] , h[N] , cnt , ans[N] , p[N];
int L[N] , R[N];
vector< int > vec[N];

struct BIT
{
	int s[N];
	int Lowbit(int x) {return x & -x;}
	void Upt(int x , int d) {for(; x <= n; x += Lowbit(x)) s[x] += d;}
	int Query(int x) {int res = 0; for(; x; x -= Lowbit(x)) res += s[x]; return res;}
	void init() {memset(s , 0 , sizeof(s));}
} bit;

void solve()
{
	for(int i = 1; i <= n; i++)
	{
		L[i] = bit.Query(n) - bit.Query(a[i]);
		bit.Upt(a[i] , 1);
	}
	bit.init();
	for(int i = 1; i <= n; i++) vec[i].clear() , p[a[i]] = i;
	for(int i = n; i; i--)
	{
		int x = p[i] , r = x;
		for(int j = 17; ~j; j--)
		{
			int nr = r + (1 << j);
			if(nr <= n && bit.Query(nr) - L[x] <= L[x]) r = nr;
		}
		vec[r].push_back(x);
		bit.Upt(x , 1);
	}
	int delta = 0;
	bit.init();
	for(int i = 1; i <= n; i++)
	{
		delta += bit.Query(a[i]);
		ans[i] = min(ans[i] , delta);
		bit.Upt(a[i] , 1);
		for(int j = 0; j < vec[i].size(); j++) bit.Upt(a[vec[i][j]] , -1);
	}
	bit.init();
}

int main()
{
	cin >> n;
	for(int i = 1; i <= n; i++) cin >> a[i] , h[++cnt] = a[i];
	sort(h + 1 , h + cnt + 1) , cnt = unique(h + 1 , h + cnt + 1) - h - 1;
	for(int i = 1; i <= n; i++) a[i] = lower_bound(h + 1 , h + cnt + 1 , a[i]) - h;
	memset(ans , 0x3f , sizeof(ans));
	solve(); 
	for(int i = 1; i <= n; i++) a[i] = n - a[i] + 1;
	solve();
	for(int i = 1; i <= n; i++) cout << ans[i] << '\n';
	return 0;
}
/*
9
11
4
5
14
1
9
19
8
10
*/