// ============== Notes =============== //
// common bugs
// - fastio
// - int overflow (especially intermediate expressionns)
// - array bounds (indices bigger than MAXN?)
// - special cases (n=1? graph not connected?)
// - re-initialize efficiently between test cases

#include <bits/stdc++.h>
using namespace std;

typedef long long i64;
typedef pair<int, int> pii;
//const i64 inf = 998244353;
const i64 inf = 1000000007;

const int maxn = 200010;

int lef[maxn*4], rig[maxn*4], laz[maxn*4];
pii val[maxn*4];
void build(int idx, int u, int v) {
	lef[idx] = u;
	rig[idx] = v;
	laz[idx] = 0;
	val[idx] = {u, v};
	if (u == v) {
		return;
	}
	int m = u + (v-u)/2;
	build(idx*2, u, m);
	build(idx*2+1, m+1, v);
}
void down(int idx) {
	if (laz[idx]) {
		val[idx] = {val[idx].first + laz[idx], val[idx].second + laz[idx]};
		laz[idx*2] += laz[idx];
		laz[idx*2 + 1] += laz[idx];
		laz[idx] = 0;
	}
}
int x, y, w;
void update(int idx) {
	int u = lef[idx], v = rig[idx], m = u + (v-u)/2;
	if (x <= u && v <= y) {
		laz[idx] += w;
		return;
	}
	down(idx);
	if (x <= m) {
		update(idx*2);
	}
	if (m < y) {
		update(idx*2 + 1);
	}
	val[idx] = {
		min(val[idx*2].first+laz[idx*2], val[idx*2+1].first+laz[idx*2+1]),
		max(val[idx*2].second+laz[idx*2], val[idx*2+1].second+laz[idx*2+1])
	};
}
pii bas;
pii query(int idx) {
	int u = lef[idx], v = rig[idx], m = u + (v-u)/2;
	if (x <= u && v <= y) {
		return {val[idx].first + laz[idx], val[idx].second + laz[idx]};
	}
	down(idx);
	pii res = bas;
	if (x <= m) {
		pii tmp = query(idx*2);
		res.first = min(res.first, tmp.first);
		res.second = max(res.second, tmp.second);
	}
	if (m < y) {
		pii tmp = query(idx*2+1);
		res.first = min(res.first, tmp.first);
		res.second = max(res.second, tmp.second);
	}
	return res;
}

int main() {
	static vector<int> pos[maxn];
	int n, k;
	cin >> n;
	for (int i = 1; i <= n; ++i) {
		scanf("%d", &k);
		pos[k].push_back(i);
	}
	static int A[maxn], B[maxn];
	//static int ans[maxn];
	build(1, 1, n);
	for (int i = 1; i <= n; ++i) {
		for (int j = 0; j < pos[i].size(); ++j) {
			x = 1;
			y = pos[i][j] - 1;
			bas = {0, 0};
			pii a = query(1);

			x = pos[i][j];
			y = n;
			bas = {maxn, -maxn};
			pii b = query(1);

			A[x] = (b.second - a.first) / 2;
		}
		for (int j = 0; j < pos[i].size(); ++j) {
			x = pos[i][j];
			y = n;
			w = -2;
			update(1);
		}
	}

	build(1, 1, n);
	for (int i = n; i > 0; --i) {
		for (int j = 0; j < pos[i].size(); ++j) {
			x = 1;
			y = pos[i][j] - 1;
			bas = {0, 0};
			pii a = query(1);

			x = pos[i][j];
			y = n;
			bas = {maxn, -maxn};
			pii b = query(1);

			B[x] = (b.second - a.first - 1) / 2;
		}
		for (int j = 0; j < pos[i].size(); ++j) {
			x = pos[i][j];
			y = n;
			w = -2;
			update(1);
		}
	}

	for (int i = 1; i <= n; ++i) {
		printf("%d ", max(A[i], B[i]));
	}
	puts("");
	return 0;
}
