#include "Anna.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(a, b) for(int a = 0; a < (b); ++a)
#define st first
#define nd second
#define pb push_back
#define all(a) a.begin(), a.end()
namespace {
int n, l, r, ile, aktl;
vector<int>T;
vector<int>pos;
vector<bool>bits;
ll ileb(ll dlu) {
ll a=dlu*(dlu+1)/2;
ll k=1;
while((1ll<<k)<a) ++k;
return k;
}
pair<ll,ll>desz(ll dlu, ll x) {
for(ll i=0; i<dlu; ++i) {
if(x>=(dlu-i)) {
x-=dlu-i;
continue;
}
return {i, i+x};
}
return {-1, -1};
}
ll szyf(ll dlu, pair<ll,ll>x) {
ll k=x.nd-x.st;
for(ll i=0; i<x.st; ++i) k+=dlu-i;
return k;
}
void check() {
++ile;
ll k=0;
rep(i, bits.size()) if(bits[i]) k|=1ll<<(ll)i;
pair<ll,ll>p=desz(pos.size(), k);
int a=p.st, b=p.nd;
vector<int>tmp;
bool zawiera=true;
rep(i, pos.size()) if((i<a || i>b) && (l<=pos[i] && pos[i]<=r)) zawiera=false;
if(zawiera) {
SendA(1);
rep(i, pos.size()) if(pos[a]<=pos[i] && pos[i]<=pos[b]) tmp.pb(pos[i]);
} else {
SendA(0);
rep(i, pos.size()) if(pos[a]>pos[i] || pos[i]>pos[b]) tmp.pb(pos[i]);
}
pos=tmp;
bits.clear();
}
int gentr(int d, int x) {
int l=bits[aktl++];
int r=bits[aktl++];
int cnt=0;
if(l) {
int k=gentr(d+1, x);
x+=k;
cnt+=k;
}
T[x]=d;
x+=1;
cnt+=1;
if(r) {
int k=gentr(d+1, x);
x+=k;
cnt+=k;
}
return cnt;
}
}
void InitA(int _N, int _L, int _R) {
n=_N; l=_L; r=_R;
ile=0;
pos.clear();
bits.clear();
rep(i, n) pos.pb(i);
}
void ReceiveA(bool x) {
bits.pb(x);
assert(ileb(pos.size())<40);
if(bits.size()==ileb(pos.size()) && ile<18) check();
}
int Answer() {
T.resize(pos.size());
aktl=0;
gentr(0, 0);
pair<int,int>mi={n, n};
rep(i, pos.size()) if(l<=pos[i] && pos[i]<=r) mi=min(mi, {T[i], pos[i]});
return mi.nd;
}
//???
#include "Bruno.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(a, b) for(int a = 0; a < (b); ++a)
#define st first
#define nd second
#define pb push_back
#define all(a) a.begin(), a.end()
namespace {
const int LIM=1e6+7;
int lewo[LIM], prawo[LIM], odw[LIM], n, ile;
pair<int,int>xd;
vector<int>T, pos;
ll ileb(ll dlu) {
ll a=dlu*(dlu+1)/2;
ll k=1;
while((1ll<<k)<a) ++k;
return k;
}
pair<ll,ll>desz(ll dlu, ll x) {
for(ll i=0; i<dlu; ++i) {
if(x>=(dlu-i)) {
x-=dlu-i;
continue;
}
return {i, i+x};
}
return {-1, -1};
}
ll szyf(ll dlu, pair<ll,ll>x) {
ll k=x.nd-x.st;
for(ll i=0; i<x.st; ++i) k+=dlu-i;
return k;
}
void send() {
int m=pos.size();
vector<pair<int,int>>P, S;
rep(i, m) {
lewo[i]=prawo[i]=i;
odw[i]=0;
P.pb({T[pos[i]], i});
}
sort(all(P));
reverse(all(P));
for(auto i : P) {
int l=i.nd, r=i.nd;
if(l && odw[l-1]) {
lewo[r]=lewo[l-1];
prawo[lewo[r]]=r;
l=lewo[r];
}
if(r<m-1 && odw[r+1]) {
prawo[l]=prawo[r+1];
lewo[prawo[l]]=l;
r=prawo[l];
}
odw[i.nd]=1;
S.pb({l, r});
}
pair<int,int>mi={LIM, LIM};
rep(i, m) {
int d=S[i].nd-S[i].st+1;
mi=min(mi, {max(d, (int)pos.size()-d), i});
}
xd=S[mi.nd];
ll k=szyf(pos.size(), S[mi.nd]);
assert(ileb(pos.size()));
rep(i, ileb(pos.size())) if(k&(1ll<<(ll)i)) SendB(1); else SendB(0);
}
void sendtr(int l, int r) {
if(l==r) {
SendB(0);
SendB(0);
return;
}
pair<int,int>mi={n, n};
for(int i=l; i<=r; ++i) mi=min(mi, {T[pos[i]], i});
int a=0, b=0;
if(l<mi.nd) a=1;
if(mi.nd<r) b=1;
SendB(a);
SendB(b);
if(a) sendtr(l, mi.nd-1);
if(b) sendtr(mi.nd+1, r);
}
}
void InitB(int _N, vector<int>_T) {
n=_N; ile=0;
T=_T;
pos.clear();
rep(i, n) pos.pb(i);
send();
}
void ReceiveB(bool y) {
++ile;
vector<int>tmp;
if(y) {
rep(i, pos.size()) if(xd.st<=i && i<=xd.nd) tmp.pb(pos[i]);
} else {
rep(i, pos.size()) if(xd.st>i || i>xd.nd) tmp.pb(pos[i]);
}
pos=tmp;
if(ile<18) {
send();
return;
}
sendtr(0, (int)pos.size()-1);
}
