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

using ll = long long;

constexpr int inf = (1 << 30) - 1;

struct Fenwick {
    int size;
    vector<int> pts, data;
    Fenwick() : size(), pts() {}

    void add_pt(int y) {
        pts.push_back(y);
    }
    void build() {
        sort(begin(pts), end(pts));
        pts.erase(unique(begin(pts), end(pts)), end(pts));
        size = (int)pts.size();
        data.assign(size + 1, inf);
    }

    void add(int y, int val) {
        int k = lower_bound(begin(pts), end(pts), y) - begin(pts) + 1;
        while (k <= size) {
            data[k] = min(data[k], val);
            k += k & -k;
        }
    }
    int pref(int y) {
        int k = lower_bound(begin(pts), end(pts), y) - begin(pts);
        int ret = inf;
        while (k > 0) {
            ret = min(ret, data[k]);
            k -= k & -k;
        }
        return ret;
    }
};

int solve(const vector<int>& X, const vector<int>& Y, const vector<int>& Z) {
    const int N = (int)X.size();

    const int Xmax = *ranges::max_element(X);
    const int Xmin = *ranges::min_element(X);
    const int Xn = Xmax - Xmin + 1;
    vector<Fenwick> fen(Xn + 1);
    for (int i = 0; i < N; ++i) {
        int k = X[i] - Xmin + 1;
        while (k < Xn) {
            fen[k].add_pt(Y[i]);
            k += k & -k;
        }
    }
    for (auto& f : fen) {
        f.build();
    }

    const int Zmin = *ranges::min_element(Z);
    vector<int> start(N + 1), list(N);
    for (int i = 0; i < N; ++i) {
        start[Z[i] - Zmin] += 1;
    }
    for (int i = 0; i < N; ++i) {
        start[i + 1] += start[i];
    }
    for (int i = 0; i < N; ++i) {
        list[--start[Z[i] - Zmin]] = i;
    }

    int ret = 0;
    for (int z = 0; z < N; ++z) {
        for (int i = start[z]; i < start[z + 1]; ++i) {
            const int k = list[i];
            for (int x = X[k] - Xmin; x > 0; x -= x & -x) {
                ret = max(ret, k - fen[x].pref(Y[k]));
            }
        }
        for (int i = start[z]; i < start[z + 1]; ++i) {
            const int k = list[i];
            for (int x = X[k] - Xmin + 1; x < Xn; x += x & -x) {
                fen[x].add(Y[k], k);
            }
        }
    }
    return ret;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int N;
    cin >> N;
    vector<int> A(N);
    for (auto& x : A) {
        cin >> x;
    }

    for (int k = 0; k <= 3; ++k) {
        vector<int> X(N + 1), Y(N + 1), Z(N + 1);
        for (int i = 0; i < N; ++i) {
            X[i + 1] = X[i];
            Y[i + 1] = Y[i];
            Z[i + 1] = Z[i];
            if (A[i] == 0) {
                X[i + 1] += 1;
                Y[i + 1] += 1;
                Z[i + 1] += 1;
            } else {
                (A[i] == 1 ? X : (A[i] == 2 ? Y : Z))[i + 1] -= 1;
            }
        }
        if (k < 3) {
            for (auto& x : A) {
                if (x == k + 1) {
                    x = 0;
                } else if (x == 0) {
                    x = k + 1;
                }
            }
        }
        cout << solve(X, Y, Z) << " \n"[k == 3];
    }

    return 0;
}