#include <iostream>
#include <vector>
#include <array>
#define vi vector<int>
#define pii pair<int, int>
#define fst first
#define snd second

using namespace std;

const int SZ = (1 << 19) + 5, INF = (1e9) + 7;

int N, ans[200001];
vi idx[200001];

array<int, 4> seg[2][SZ];
int lz[2][SZ];

array<int, 4> merge(const array<int, 4>& L, const array<int, 4>& R)
{
	return {min(L[0], R[0]), max(L[1], R[1]), min(L[2], R[2]), max(L[3], R[3])};
}

inline void prop(int t, int idx, int L, int R)
{
	if (lz[t][idx])
	{
		for (int i = 0; i < 4; i++) 
		{
			if (seg[t][idx][i] > -INF && seg[t][idx][i] < INF) seg[t][idx][i] += lz[t][idx];
		}
		if (L < R)
		{
			lz[t][2 * idx] += lz[t][idx];
			lz[t][2 * idx + 1] += lz[t][idx];
		}
		lz[t][idx] = 0;
	}
}

void build(int t, int idx, int L, int R)
{
	seg[t][idx][0] = seg[t][idx][2] = INF;
	seg[t][idx][1] = seg[t][idx][3] = -INF;
	if (L == R) 
	{
		seg[t][idx][(L & 1) << 1] = 0;
		seg[t][idx][(L & 1) << 1 | 1] = 0;
	}
	else if (L < R)
	{
		int M = L + R >> 1;
		build(t, 2 * idx, L, M);
		build(t, 2 * idx + 1, M + 1, R);
		seg[t][idx] = merge(seg[t][2 * idx], seg[t][2 * idx + 1]);
	}
}

void upd(int t, int idx, int L, int R, int l, int r, int v)
{
	l = max(L, l); r = min(R, r); prop(t, idx, L, R);
	if (l <= r)
	{
		if (L == l && R == r) {lz[t][idx] += v; prop(t, idx, L, R);}
		else
		{
			int M = L + R >> 1;
			upd(t, 2 * idx, L, M, l, r, v);
			upd(t, 2 * idx + 1, M + 1, R, l, r, v);
			seg[t][idx] = merge(seg[t][2 * idx], seg[t][2 * idx + 1]);
		}
	}
}

array<int, 4> qry(int t, int idx, int L, int R, int l, int r)
{
	l = max(L, l); r = min(R, r);
	if (l <= r)
	{
		prop(t, idx, L, R);
		if (L == l && R == r) {return seg[t][idx];}
		else
		{
			int M = L + R >> 1;
			return merge(qry(t, 2 * idx, L, M, l, r), qry(t, 2 * idx + 1, M + 1, R, l, r));
		}
	}
	return {INF, -INF, INF, -INF};
}

int main()
{
	cin >> N;
	for (int i = 1; i <= N; i++)
	{
		int x; cin >> x;
		idx[x].push_back(i);
	}
	build(0, 1, 0, N);
	build(1, 1, 0, N);
	for (int i = 1; i <= N; i++)
	{
		upd(i & 1, 1, 0, N, i, N, -1);
	}
	for (int i = 1; i <= N; i++)
	{
		for (const auto &x : idx[i])
		{
			for (int j = 0; j < 2; j++)
			{
				array<int, 4> A = qry(j, 1, 0, N, 0, x - 1), B = qry(j, 1, 0, N, x, N);
				ans[x] = max(ans[x], max(B[1], B[3]) - A[j << 1]);
				ans[x] = max(ans[x], A[j << 1 | 1] - min(B[0], B[2]));		
			}	
		}
		for (const auto &x : idx[i]) 
		{
			for (int j = 0; j < 2; j++) upd(j, 1, 0, N, x, N, 1);
		}
		for (const auto &x : idx[i])
		{
			for (int j = 0; j < 2; j++)
			{
				upd(j, 1, 0, N, x, N, -1);
				array<int, 4> A = qry(j, 1, 0, N, 0, x - 1), B = qry(j, 1, 0, N, x, N);
				ans[x] = max(ans[x], max(B[1], B[3]) - A[j << 1]);
				ans[x] = max(ans[x], A[j << 1 | 1] - min(B[0], B[2]));
				upd(j, 1, 0, N, x, N, 1);
			}
		}
	}
	for (int i = 1; i <= N; i++)
	{
		cout << ans[i] << " \n"[i == N];
	}
	return 0;
}