#include"bits/stdc++.h"
#include"grader.h"
using namespace std;
using ll=long long;
using ld=long double;
using str=string;
template<class T,class U>using P=pair<T,U>;
using pi=P<int,int>;
template<class T>using V=vector<T>;
using vi=V<int>;
using vl=V<ll>;
using vvi=V<vi>;
using vpi=V<pair<int,int>>;
template<class T>int lwb(V<T>&a,T b){return int(lb(all(a),b)-begin(a));}
template<class T>int lwb(T a[],int n,T b){return int(lb(a,a+n,b)-a);}
template<class T>int upb(V<T>&a,T b){return int(ub(all(a),b)-begin(a));}
template<class T>int upb(T a[],int n,T b){return int(ub(a,a+n,b)-a);}
template<class T>ll sum(V<T>&a){return accumulate(all(a),0ll);}
template<class T>ll sum(T a[],int n){return accumulate(a,a+n,0ll);}
template<class T>T MAX(V<T>&a){return *max_element(all(a));}
template<class T>T MAX(T a[],int n){return *max_element(a,a+n);}
template<class T>T MIN(V<T>&a){return *min_element(all(a));}
template<class T>T MIN(T a[],int n){return *min_element(a,a+n);}
template<class T,class U>ifstream&operator>>(istream&in,P<T,U>a){return in>>a.first>>a.second;}
#define sz(x)int(size(x))
#define all(x)begin(x),end(x)
#define lla(x)rbegin(x),rend(x)
#define lb lower_bound
#define ub upper_bound
#define FOR(i,a,b)for(int i=(a);i<(b);i++)
#define F0R(i,a)FOR(i,0,a)
#define ROF(i,a,b)for(int i=(b)-1;(a)<=i;i--)
#define R0F(i,a)ROF(i,0,a)
#define rep(a)F0R(_,a)
#define each(a,x)for(auto&a:x)
#define con const int
int szs[2];
int sn[2];
int N;
vi get(int x, int y, int z){
vi r;
FOR(i, 1, x + y + 1){
r.push_back(z ^ (i > x));
}
return r;
}
int zr(){
if (sn[0] + szs[1] - sn[1] + 1 <= N / 2 + 1){
return isSubsequence(get(sn[0] + 1, szs[1] - sn[1], 0));
} else {
return !isSubsequence(get(sn[1] + 1, szs[0] - sn[0], 1));
}
}
vi findSequence(int n){
N = n;
vi q;
rep(N / 2 + 1){
q.push_back(1);
if (isSubsequence(q)){
szs[1] ++;
szs[0] = N - szs[1];
}
}
if (szs[1] == N / 2 + 1){
vi().swap(q);
szs[0] = szs[1] = 0;
rep(N / 2 + 1){
q.push_back(0);
if (isSubsequence(q)){
szs[0] ++;
szs[1] = N - szs[0];
}
}
}
vi ans;
rep(N){
ans.push_back(!zr());
sn[ans.back()] ++;
}
return ans;
}
