#include<bits/stdc++.h>
#ifndef cpismylifeOwO
#include "grader.h"
#endif // cpismylifeOwO
using namespace std;
const long long mod = 1e9 + 7;
const int MaxN = 1e6 + 5;
#ifdef cpismylifeOwO
#define REP(i, n) for (int i = 0, _n = (n); i < _n; ++i)
int N;
vector <int> v;
int L;
bool isSubsequence(vector <int> t) {
assert((int) t.size() <= N);
L = max(L, (int) t.size());
int cur = 0;
for (int i: t) {
while (cur < N && v[cur] != i) ++cur;
if (cur == N) return false;
++cur;
}
return true;
}
#endif // cpismylifeOwO
vector<int> rev(vector<int> a, bool sw)
{
if (sw)
{
for (int x = 0; x < (int)a.size(); x++)
{
a[x] ^= 1;
}
}
return a;
}
struct Change
{
int prev, p1, p2;
Change() = default;
Change(int _prev, int _p1, int _p2)
{
prev = _prev;
p1 = _p1;
p2 = _p2;
}
};
int nxt[MaxN];
int F[MaxN][3];
pair<int, int> Fnxt[MaxN][3];
vector<int> findSequence(int n)
{
vector<int> now, res;
now.push_back(0);
while ((int)now.size() <= (n / 2) + 1 && isSubsequence(now))
{
now.push_back(0);
}
bool sw = false;
int cntleft = 0, cnt2 = 0;
if ((int)now.size() > (n / 2) + 1)
{
sw = true;
now.clear();
now.push_back(1);
while (isSubsequence(now))
{
now.push_back(1);
}
now.pop_back();
cntleft = n - (int)now.size();
res.push_back(2);
cnt2++;
for (int x : now)
{
res.push_back(!x);
res.push_back(2);
cnt2++;
}
}
else
{
sw = false;
now.pop_back();
cntleft = n - (int)now.size();
res.push_back(2);
cnt2++;
for (int x : now)
{
res.push_back(x);
res.push_back(2);
cnt2++;
}
}
while (cnt2 > 1 && cntleft)
{
vector<Change> lst2;
now.clear();
int cur0 = (int)res.size(), cur1 = cur0;
F[(int)res.size()][0] = 0;
F[(int)res.size()][1] = 0;
F[(int)res.size()][2] = 0;
for (int x = (int)res.size() - 1; x >= 0; x--)
{
nxt[x] = max(cur0, cur1);
if (!res[x])
{
cur0 = x;
}
else
{
cur1 = x;
}
F[x][0] = F[x][1] = F[x][2] = 1e9;
int cnt0 = 0, cnt1 = 0, cntline = 0;
bool isp = false, isp2 = ((int)res.size() == 2);
for (int y = x; y < (int)res.size(); y++)
{
cnt0 += (res[y] == 0);
cnt1 += (res[y] != 0);
cntline += (y > x && ((res[y] == 0) == (res[y - 1] == 0)));
isp &= (res[y] != 2);
if (cnt0 && (y == (int)res.size() - 1 || res[y + 1] == 1) && F[x][0] > F[y + 1][1] + 1)
{
F[x][0] = F[y + 1][1] + 1;
Fnxt[x][0] = make_pair(y + 1, 1);
}
if (cnt0 && (y == (int)res.size() - 1 || res[y + 1] == 1) && F[x][0] > F[y + 1][2] + 1)
{
F[x][0] = F[y + 1][2] + 1;
Fnxt[x][0] = make_pair(y + 1, 2);
}
if (!isp2 && cntline)
{
if (F[x][1] < F[y + 1][0] + 1)
{
F[x][1] = F[y + 1][0] + 1;
Fnxt[x][1] = make_pair(y + 1, 0);
}
if (F[x][1] < F[y + 1][2] + 1)
{
F[x][1] = F[y + 1][2] + 1;
Fnxt[x][1] = make_pair(y + 1, 2);
}
}
if (cnt1 && !isp && (y == (int)res.size() - 1 || res[y + 1] == 0))
{
if (F[x][2] > F[y + 1][0] + 1)
{
F[x][2] = F[y + 1][0] + 1;
Fnxt[x][2] = make_pair(y + 1, 0);
}
if (F[x][2] > F[y + 1][1] + 1)
{
F[x][2] = F[y + 1][1] + 1;
Fnxt[x][2] = make_pair(y + 1, 1);
}
}
}
}
int k = max(cur0, cur1), pre = -1;
while (k < (int)res.size())
{
for (int x = pre + 1; x <= k; x++)
{
if (res[x] == 2)
{
lst2.push_back(Change(x - pre, x, (int)now.size() - 1));
}
}
pre = k;
now.push_back(res[k]);
k = nxt[k];
}
for (int x = pre + 1; x < (int)res.size(); x++)
{
if (res[x] == 2)
{
lst2.push_back(Change(x - pre, x, (int)now.size() - 1));
}
}
int add = 0;
for (Change& u : lst2)
{
vector<int> ask;
for (int x = 0; x <= u.p2; x++)
{
ask.push_back(now[x]);
}
for (int x = 1; x <= u.prev; x++)
{
ask.push_back(1);
}
if (u.p1 + add + 1 < (int)res.size())
{
int v = u.p1 + 1;
pair<int, int> mi = min(make_pair(F[v][0], 0), min(make_pair(F[v][1], 1), make_pair(F[v][2], 2)));
int t = mi.second;
while (v + add < (int)res.size())
{
int con = Fnxt[v][t].first;
if (!t)
{
for (int x = v + add; x < con + add; x++)
{
if (res[x] == 0)
{
ask.push_back(0);
}
}
}
else if (t == 1)
{
for (int x = v + add; x < con + add; x++)
{
if (x == v + add || ((res[x] > 0) != (res[x - 1] > 0)))
{
ask.push_back(res[x]);
}
}
}
else
{
for (int x = v + add; x < con + add; x++)
{
if (res[x] == 1)
{
ask.push_back(1);
}
}
}
t = Fnxt[v][t].second;
v = con;
}
}
if (isSubsequence(rev(ask, sw)))
{
res.insert(res.begin() + add + u.p1, 1);
add++;
cntleft--;
}
else
{
res.erase(res.begin() + add + u.p1);
add--;
cnt2--;
}
}
}
vector<int> tmp = res;
res.clear();
for (int x : tmp)
{
if (x == 2)
{
for (int y = 1; y <= cntleft; y++)
{
res.push_back(1);
}
cntleft = 0;
}
else
{
res.push_back(x);
}
}
return rev(res, sw);
}
#ifdef cpismylifeOwO
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
long long rand(long long l, long long h) { return uniform_int_distribution <long long> (l, h) (rng); }
int main(void) {
freopen("stub.INP", "r", stdin);
//freopen("stub.OUT", "w", stdout);
ios_base::sync_with_stdio(false); cin.tie(nullptr); // cout.tie(nullptr);
bool type, isprinted;
cin >> N >> type >> isprinted;
v.resize(N);
if (!type)
{
for (int x = 0; x < N; x++) cin >> v[x];
}
else REP(i, N) v[i] = rand(0, 1);
vector <int> res = findSequence(N);
cout << L << '\n';
if (isprinted)
{
for (int x : v) cout << x << " ";
cout << '\n';
for (int x : res) cout << x << ' ';
cout << "\n";
}
bool chk = ((int)res.size() == N);
if (chk)
{
for (int x = 0; x < N; x++)
{
chk &= (v[x] == res[x]);
}
}
cout << chk << "\n";
return (0^0);
}
#endif // cpismylifeOwO
