#include <bits/stdc++.h>
using namespace std;
/*
John Watson
https://codeforces.com/profile/quangminh98
Mua Code nhu mua Florentino !!
*/
#define faster() ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define ll long long
const int maxn = 2e5 + 9;
const int segsize = 4 * maxn;
int n;
int arr[maxn];
class SegmentTree
{
struct Node
{
int sum;
int lazy;
Node(int sum = 0, int lazy = -1) : sum(sum), lazy(lazy) {}
Node operator + (const Node& other)
{
Node res;
res.sum = sum + other.sum;
res.lazy = -1;
return res;
}
};
vector<Node> st;
int n;
void pass(int head, int l, int r)
{
if (st[head].lazy == -1 || l == r) return;
int mid = l + r >> 1;
st[2 * head].sum = (mid - l + 1) * st[head].lazy;
st[2 * head + 1].sum = (r - mid) * st[head].lazy;
st[2 * head].lazy = st[head].lazy;
st[2 * head + 1].lazy = st[head].lazy;
st[head].lazy = -1;
}
void update(int head, int l, int r, int u, int v, int val)
{
pass(head, l, r);
if (l > v || r < u) return;
if (u <= l && r <= v)
{
st[head].sum = (r - l + 1) * val;
st[head].lazy = val;
return;
}
int mid = l + r >> 1;
update(2 * head, l, mid, u, v, val);
update(2 * head + 1, mid + 1, r, u, v, val);
st[head] = st[2 * head] + st[2 * head + 1];
}
int query(int head, int l, int r, int u, int v)
{
if (u > v) return -1;
pass(head, l, r);
if (l > v || r < u) return -1;
if (l == r) return (st[head].sum > 0 ? l : -1);
int mid = l + r >> 1;
if (st[2 * head + 1].sum > 0)
return query(2 * head + 1, mid + 1, r, u, v);
return query(2 * head, l, mid, u, v);
}
int getpos(int head, int l, int r, int pos)
{
if (l == r)
return st[head].sum;
int mid = l + r >> 1;
if (pos <= mid)
return getpos(2 * head, l, mid, pos);
return getpos(2 * head + 1, mid + 1, r, pos);
}
public:
SegmentTree(int n = 0) : n(n) { st.resize(segsize, Node(0, -1)); }
void update(int u, int v, int val) { update(1, 1, n, u, v, val); }
int query(int u, int v) { return query(1, 1, n, u, v); }
int getpos(int pos) { return getpos(1, 1, n, pos); }
};
void solve_2()
{
SegmentTree seg[3];
for (int i = 1; i < 3; i++) seg[i] = SegmentTree(n);
for (int i = 1; i <= n; i++)
{
int pos = seg[arr[i]].query(1, i - 1);
if (pos != -1)
{
seg[arr[i]].update(pos, i - 1, 1);
seg[3 - arr[i]].update(pos, i - 1, 0);
}
seg[arr[i]].update(i, i, 1);
}
for (int i = 1; i <= n; i++)
{
int pos1 = seg[1].getpos(i);
int pos2 = seg[2].getpos(i);
cout << (pos1 == 1 ? 1 : 2) << '\n';
}
}
void solve_1()
{
for (int i = 1; i <= n; i++)
{
int mx = -1;
for (int j = 1; j < i; j++)
if (arr[j] == arr[i])
mx = max(mx, j);
if (mx != -1)
for (int j = mx; j < i; j++)
arr[j] = arr[i];
}
for (int i = 1; i <= n; i++)
cout << arr[i] << '\n';
}
signed main()
{
if (fopen("test.inp", "r"))
{
freopen("test.inp", "r", stdin);
freopen("test.out", "w", stdout);
}
faster();
cin >> n;
bool sub2 = true;
for (int i = 1; i <= n; i++)
{
cin >> arr[i];
if (arr[i] > 2) sub2 = false;
}
if (n <= 2000)
{
solve_1();
return 0;
}
if (sub2 == true)
{
solve_2();
return 0;
}
return 0;
}
