#include "grader.h"
#include <bits/stdc++.h>
using namespace std;
#define rep(i, a, b) for (int i = a; i < (b); ++i)
#define per(i, a, b) for (int i = b - 1; i >= (a); --i)
#define trav(a, x) for (auto &a : x)
#define all(x) x.begin(), x.end()
#define sz(x) x.size()
#define pb push_back
#define umap unordered_map
#define uset unordered_set
typedef pair<int, int> ii;
typedef pair<int, ii> iii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<vi> vvi;
typedef long long ll;
const int INF = 1000000007;
vector<int> findSequence(int n) {
vector<int> ans(n, -1);
vi subseq;
int left[2], taken[2];
taken[0] = taken[1] = 0;
int zeros, ones, len = n / 2 + 1, small = 0, big = 1;
zeros = -1;
rep(i, 1, len + 1) {
subseq.pb(0);
if (!isSubsequence(subseq)) {
zeros = i - 1;
break;
}
}
if (zeros == -1) {
subseq.clear();
rep(i, 1, len + 1) {
subseq.pb(1);
if (!isSubsequence(subseq)) {
ones = i - 1;
break;
}
}
zeros = n - ones;
swap(small, big);
} else
ones = n - zeros;
left[0]=zeros;
left[1]=ones;
per(i, 0, n) {
vi query;
int add;
query.clear();
rep(j, 0, left[big]) query.pb(big);
rep(j, 0, taken[small] + 1) query.pb(small);
if (sz(query) <= len) {
if (isSubsequence(query))
add = small;
else
add = big;
}
else {
query.clear();
rep(j, 0, left[small]) query.pb(small);
rep(j, 0, taken[big] + 1) query.pb(big);
if (isSubsequence(query))
add = big;
else
add = small;
}
--left[add];
++taken[add];
subseq.insert(subseq.begin(), add);
ans[i] = add;
}
return ans;
}
