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

const int INF = 1e9 + 20;
const int MAX_N = 1e5 + 20;
int a[MAX_N];
int fen[MAX_N * 2];
array<int, 5> p[MAX_N];
array<int, 5> tmp[MAX_N];
int n, res;

void update(int pos, int val) {
  for (int i = pos; i <= n * 2 + 1; i += i & (-i)) {
    fen[i] = min(fen[i], val);
  }
}

int get(int pos) {
  int res = INF;
  for (int i = pos; i > 0; i -= i & (-i)) {
    res = min(res, fen[i]);
  }
  return res;
}

void clear(int pos) {
  for (int i = pos; i <= n * 2 + 1; i++) {
    fen[i] = INF;
  }
}

bool cmp2(array<int, 5> a1, array<int, 5> a2) {
  if (a1[1] != a2[1]) {
    return a1[1] < a2[1];
  }
  else {
    return a1[3] > a2[3];
  }
}

void dnc(int l, int r) {
  if (l == r) {
    return;
  }
  int m = (l + r) >> 1;
  dnc(l, m);
  dnc(m + 1, r);
  for (int i = l; i <= r; i++) {
    for (int j = 0; j < 5; j++) {
      tmp[i][j] = p[i][j];
    }
  }
  int l1 = l;
  int r1 = m;
  int l2 = m + 1;
  int r2 = r;
  int pt = l;
  while (l1 <= r1 || l2 <= r2) {
    if (l2 > r2 || (l1 <= r1 && cmp2(tmp[l1], tmp[l2]))) {
      p[pt++] = tmp[l1++];
    }
    else {
      p[pt++] = tmp[l2++];
    }
  }
  int cur = l;
  //cout << "dnc " << l << " " << r << '\n';
  for (int i = l; i <= r; i++) {
    while (p[cur][1] < p[i][1]) {
      if (p[cur][4] <= m) {
        //cout << "update " << cur << " " << p[cur][2] << " " << p[cur][3] << '\n';
        update(p[cur][2], p[cur][3]);
      }
      cur++;
    }
    if (p[i][4] > m) {
      //cout << "get " << p[i][3] << " " << get(p[i][2] - 1) << " " << p[i][3] - get(p[i][2] - 1) << '\n';
      res = max(res, p[i][3] - get(p[i][2] - 1));
    }
  }
  for (int i = l; i <= r; i++) {
    clear(p[i][2]);
  }
  // for (int i = l; i <= r; i++) {
  //   for (int j = 0; j < 5; j++) {
  //     cout << p[i][j] << " ";
  //   }
  //   cout << '\n';
  // }
  // cout << '\n';
}

bool cmp(array<int, 5> a1, array<int, 5> a2) {
  if (a1[0] != a2[0]) {
    return a1[0] < a2[0];
  }
  else {
    return a1[3] > a2[3];
  }
}

int main() {
  cin >> n;
  for (int i = 1; i <= n * 2 + 1; i++) {
    fen[i] = INF;
  }
  for (int i = 1; i <= n; i++) {
    cin >> a[i];
  }
  for (int iter = 0; iter < 4; iter++) {
    res = 1;
    for (int i = 0; i <= n; i++) {
      p[i][3] = i;
    }
    p[0][0] = 0;
    p[0][1] = 0;
    p[0][2] = n + 1;
    for (int i = 1; i <= n; i++) {
      for (int j = 0; j < 3; j++) {
        p[i][j] = p[i - 1][j];
      }
      if (a[i] == iter) {
        res = 1;
        for (int j = 0; j < 3; j++) {
          p[i][j]++;
        }
      }
      else {
        p[i][a[i] - (a[i] > iter)]--;
      }
    }
    sort(p, p + n + 1, cmp);
    for (int i = 0; i <= n; i++) {
      p[i][4] = i;
    }
    // for (int i = 0; i <= n; i++) {
    //   for (int j = 0; j < 5; j++) {
    //     cout << p[i][j] << " ";
    //   }
    //   cout << '\n';
    // }
    // cout << '\n';
    dnc(0, n);
    cout << res << " ";
  }
  return 0;
}