#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#define ALL(x) x.begin(), x.end()
#define SZ(x) ((int)x.size())
#define fastio ios::sync_with_stdio(0), cin.tie(0);
using namespace std;

#ifdef LOCAL
#define cout cout << "\033[0;32m"
#define cerr cerr << "\033[0;31m"
#define endl "\n" << "\033[0m"
#else
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx,avx2,sse,sse2,sse3,sse4,popcnt")
#define endl "\n"
#endif

const int MAX_N = 2e5+100;
const int INF = 2e9;
const int P = 1e5+10;

// declare
int n;
vector<int> v;
vector<int> d[4][4];

struct BinaryIndexTree{
	vector<int> BIT;
	vector<int> backup;

	BinaryIndexTree(int n){
		BIT.assign(n, INF);
		return;
	}

	void update(int pos, int val){
		pos += P;
		backup.push_back(pos);
		for (int i=pos ; i<SZ(BIT) ; i+=i&-i) BIT[i] = min(BIT[i], val);
	}

	int query(int pos){
		pos += P;
		int ret = INF;
		for (int i=pos ; i ; i-=i&-i) ret = min(ret, BIT[i]);
		return ret;
	}

	void reset(){
		for (auto pos : backup) for (int i=pos ; i<SZ(BIT) ; i+=i&-i) BIT[i] = INF;
		backup.clear();
	}
};

/*
1. 先根據一維遞增排序
2. 在根據二維遞減排序
*/

void solve1(){

	// init
	for (int i=0 ; i<4 ; i++){
		for (int j=0 ; j<4 ; j++){
			d[i][j].resize(MAX_N);
		}
	}

	// input
	cin >> n;
	v.resize(n);
	for (int i=0 ; i<n ; i++) cin >> v[i];

	// process
	for (int i=0 ; i<n ; i++) for (int j=0 ; j<4 ; j++) for (int k=0 ; k<4 ; k++){
		if (v[i]==j) d[j][k][i]++;
		if (v[i]==k) d[j][k][i]--;
	}
	for (int i=1 ; i<n ; i++) for (int j=0 ; j<4 ; j++) for (int k=0 ; k<4 ; k++) d[j][k][i] += d[j][k][i-1];

	// 解決三維偏序 [l, r)
	BinaryIndexTree BIT(n*2+5);
	auto CDQ = [&](auto self, int l, int r, vector<vector<int>> &v){
		if (r-l<=1) return 0;
		int mid = (l+r)/2;
		int ans = max(self(self, l, mid, v), self(self, mid, r, v));

		vector<vector<int>> tmp;
		int i, j;
		for (i=l, j=mid ; j<r ; j++){
			while (i<mid && v[i][1]<v[j][1]){
				BIT.update(v[i][2], v[i][3]);
				tmp.push_back(v[i]);
				i++;
			}
			ans = max(ans, v[j][3]-BIT.query(v[j][2]-1));
			tmp.push_back(v[j]);
		}
		BIT.reset();
		while (i<mid){
			tmp.push_back(v[i]);
			i++;
		}
		copy(ALL(tmp), v.begin()+l);
		return ans;
	};

	for (int i=0 ; i<4 ; i++){
		vector<vector<int>> v(n);
		v.push_back({0, 0, 0, -1});
		for (int j=0 ; j<n ; j++){
			for (int k=0 ; k<4 ; k++){
				if (i==k) continue;
				v[j].push_back(d[i][k][j]);
			}
			v[j].push_back(j);
		}
		
		sort(v.begin(), v.end(), [](auto a, auto b){
			if (a[0]==b[0]) return a[1]>b[1];
			return a[0]<b[0];
		});
		int ans = CDQ(CDQ, 0, n+1, v);
		cout << ans << " ";
	}
	cout << endl;
	
    return;
}

signed main(){

    fastio;

    int t = 1;
    while (t--){
        solve1();
    }

    return 0;
}