#include "grader.h"
#define wiwihorz
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma loop-opt(on)
#define rep(i, a, b) for(int i = a; i <= b; i ++)
#define rrep(i, a, b) for(int i = b; i >= a; i--)
#define all(x) x.begin(), x.end()
#define ceil(a, b) ((a + b - 1) / (b))
using namespace std;
#define pii pair<int, int>
#define random mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count())
#ifdef wiwihorz
#define print(a...) cerr << "Line " << __LINE__ << ": ", kout("[" + string(#a) + "] = ", a)
void vprint(auto L, auto R) { while(L < R) cerr << *L << " \n"[next(L) == R], ++L;}
void kout() { cerr << endl; }
template<class T1, class ... T2> void kout(T1 a, T2 ... e) { cerr << a << " ", kout(e...);}
#else
#define print(...) 0
#define vprint(...) 0
#endif
vector <int> findSequence (int N) {
vector<int> ans, a, b, q;
int id = 0, num = -1;
int mx1 = N / 2 + 1, mx2 = (N * 3) / 4 + 1;
// get num
rep(i, 1, mx1) {
q.push_back(0);
if(!isSubsequence(q)) {
num = i - 1;
break;
}
}
if(num == -1) {
id = 1, q.clear();
rep(i, 1, mx1) {
q.push_back(1);
if(!isSubsequence(q)) {
num = i - 1;
break;
}
}
}
// get wall
rep(i, 0, num) {
q.clear();
rep(j, 1, i) q.push_back(id);
q.push_back(!id);
rep(j, 1, num - i) q.push_back(id);
if(isSubsequence(q)) a.push_back(i);
}
// get wall num
b.assign(a.size(), 0);
int sz = a.size(), tot = 0;
rep(i, 0, signed(a.size()) - 1) {
rep(j, 1, mx2 - num) {
q.clear();
rep(k, 1, a[i]) q.push_back(id);
rep(k, 1, j) q.push_back(!id);
rep(k, 1, num - a[i]) q.push_back(id);
if(!isSubsequence(q)) {
b[i] = j - 1;
tot += j - 1;
break;
}
}
}
int left = N - num - tot, cur = 0;
rep(i, 0, sz - 1) if(!b[i]) b[i] = left;
rep(i, 0, sz - 1) {
while(cur < a[i]) ans.push_back(id), cur ++;
rep(j, 1, b[i]) ans.push_back(!id);
}
while(cur < num) ans.push_back(id), cur++;
return ans;
}
