#include <bits/stdc++.h>
#define PB push_back
#define EB emplace_back
using namespace std;
typedef long long i64;
const int maxn = 200000;
int n;
int a[maxn + 5], d[maxn + 5];
i64 ans[maxn + 5];
int t[maxn + 5];
void modify(int x, int v) {
	for (; x <= n; x += x & (-x)) t[x] += v;
}
int query(int x) {
	int rs = 0;
	for (; x; x -= x & (-x)) rs += t[x];
	return rs;
}
int w[maxn + 5];
vector<int> del[maxn + 5];
int fv[maxn + 5];
void solve() {
	for (int i = 1; i <= n; i++) {
		fv[i] = query(n + 1 - a[i]);
		modify(n + 1 - a[i], 1);
	}
	memset(t, 0, sizeof(t));
	for (int i = 1; i <= n; i++) w[a[i]] = i;
	fill(del + 1, del + n + 1, vector<int>());
	for (int i = n; i; i--) {
		int p = w[i], r = p;
		for (int j = 17; ~j; j--)
			if (int nr = r + (1 << j); nr <= n && query(nr) <= fv[p] * 2) r = nr;
		del[r].PB(p);
		modify(p, 1);
	}
	memset(t, 0, sizeof(t));
	i64 nw = 0;
	for (int i = 1; i <= n; i++) {
		nw += query(a[i]);
		ans[i] = min(ans[i], nw);
		modify(a[i], 1);
		for (int x : del[i]) modify(a[x], -1);
	}
	memset(t, 0, sizeof(t));
}
int main() {
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) {
		scanf("%d", &a[i]);
		d[i] = a[i];
	}
	sort(d + 1, d + n + 1);
	for (int i = 1; i <= n; i++) a[i] = lower_bound(d + 1, d + n + 1, a[i]) - d;
	memset(ans, 127, sizeof(ans));
	solve();
	for (int i = 1; i <= n; i++) a[i] = n + 1 - a[i];
	solve();
	for (int i = 1; i <= n; i++) printf("%lld\n", ans[i]);
}