#include <bits/stdc++.h>
#include <cave.h>
using namespace std;
#define designed ios_base::sync_with_stdio(0);
#define by cin.tie(0);
#define AndreasK cout.tie(0);
//#define int long long
#define ii pair <int, int>
#define vi vector <int>
#define iii pair <int, ii>
#define vii vector <ii>
#define vc vector <char>
#define vb vector <bool>
/*int n;
int tryCombination(int a[]) {
int ansa[] = {1, 0, 0, 1};
int ansb[] = {2, 1, 0, 3};
int mn = 4;
for (int c = 0; c < n; c++) {
if (a[c] != ansa[c]) {
mn = min(mn, ansb[c]);
}
}
if (mn == 4)
mn = -1;
return mn;
}
void answer(int a[], int b[]) {
for (int c = 0; c < n; c++)
cout << a[c] << ' ';
cout << '\n';
for (int c = 0; c < n; c++)
cout << b[c] << ' ';
cout << '\n';
}*/
void exploreCave(int n) {
int a[n] = {}, b[n];
vi v(n, 0);
for (int c = 0; c < n; c++) {
int x = tryCombination(a);
if (x == -1 || x > c) {
int l = 0, r = n - 1;
while (l < r) {
int mid = (l + r) / 2;
int d[n];
for (int rr = 0; rr < n; rr++) {
if (rr > mid && v[rr] == 0) {
d[rr] = 1;
}
else if (v[rr] == 1)
d[rr] = a[rr];
else
d[rr] = 0;
}
int x = tryCombination(d);
if (x == -1)
x = n;
if (x > c) {
r = mid;
}
else
l = mid + 1;
}
b[(l + r) / 2] = c;
v[(l + r) / 2] = 1;
}
else {
int l = 0, r = n - 1;
while (l < r) {
int mid = (l + r) / 2;
int d[n];
for (int rr = 0; rr < n; rr++) {
if (rr > mid && v[rr] == 0) {
d[rr] = 1;
}
else if (v[rr] == 1)
d[rr] = a[rr];
else
d[rr] = 0;
}
int x = tryCombination(d);
if (x == -1)
x = n;
if (x > c) {
l = mid + 1;
}
else
r = mid;
}
a[(l + r) / 2] = 1;
v[(l + r) / 2] = 1;
b[(l + r) / 2] = c;
}
}
answer(a, b);
}
/*int32_t main() {
designed by AndreasK
cin >> n;
exploreCave(n);
return 0;
}*/
