#include "Anna.h"
#include <vector>
#include <bits/stdc++.h>
using namespace std;
namespace Anna{
const int SIZE=1384, COUNT=723;
struct SparseTable{
int n, lg;
vector<int> a;
vector<vector<pair<int, int>>> st;
void build(int _n, const vector<int> &_a){
n=_n; a=_a;
lg=0;
while ((1<<lg)<=n) ++lg;
st.assign(lg, vector<pair<int, int>>(n, {0, 0}));
for (int i=0; i<n; ++i) st[0][i]={a[i], i};
for (int k=1; k<lg; ++k){
for (int i=0; i+(1<<k)-1<n; ++i){
st[k][i]=min(st[k-1][i], st[k-1][i+(1<<(k-1))]);
}
}
}
int get(int l, int r){
assert(l<=r);
int k=__lg(r-l+1);
return min(st[k][l], st[k][r-(1<<k)+1]).second;
}
};
struct CartesianTree{
int n;
vector<int> left, right, par, dep;
vector<int> a;
SparseTable st;
vector<int> bin;
int root;
void gen_binary(){
bin.clear();
auto dfs=[&](auto &&self, int u) -> void {
if (left[u]!=-1) self(self, left[u]);
bin.push_back(0);
if (right[u]!=-1) self(self, right[u]);
bin.push_back(1);
};
dfs(dfs, root);
}
void dfs_dep(int u){
if (left[u]!=-1) dep[left[u]]=dep[u]+1, dfs_dep(left[u]);
if (right[u]!=-1) dep[right[u]]=dep[u]+1, dfs_dep(right[u]);
}
void build(int _n, const vector<int> &_a){
n=_n, a=_a;
st.build(n, a);
left.assign(n, -1);
right.assign(n, -1);
par.assign(n, -1);
dep.assign(n, 0);
auto dfs=[&](auto &&self, int l, int r) -> int {
if (l>r) return -1;
if (l==r) return l;
int m=st.get(l, r);
left[m]=self(self, l, m-1);
right[m]=self(self, m+1, r);
if (left[m]!=-1) par[left[m]]=m;
if (right[m]!=-1) par[right[m]]=m;
return m;
};
root=dfs(dfs, 0, n-1);
gen_binary();
dfs_dep(root);
}
int lca(int u, int v){
while (dep[u]<dep[v]) v=par[v];
while (dep[u]>dep[v]) u=par[u];
while (u!=v) u=par[u], v=par[v];
return u;
}
void build(const vector<int> &_bin){
bin=_bin;
n=(int)bin.size()/2;
vector<int> match(n*2);
stack<int> st;
for (int i=0; i<n*2; ++i){
if (bin[i]==0) st.push(i);
else match[st.top()]=i, match[i]=st.top(), st.pop();
}
left.assign(n, -1);
right.assign(n, -1);
par.assign(n, -1);
dep.assign(n, 0);
int cnt=0;
auto dfs=[&](auto &&self, int l, int r) -> int {
if (l>r) return -1;
int m=match[r];
int tl=self(self, l, m-1);
int u=cnt++;
int tr=self(self, m+1, r-1);
left[u]=tl, right[u]=tr;
if (left[u]!=-1) par[left[u]]=u;
if (right[u]!=-1) par[right[u]]=u;
return u;
};
root=dfs(dfs, 0, n*2-1);
dfs_dep(root);
}
};
int encode(pair<int, int> x){
int ans=0;
for (int i=0; i<x.first; ++i) ans+=COUNT-i;
return ans+(x.second-x.first);
}
pair<int, int> decode(int x){
for (int i=0; i<COUNT; ++i){
if (x<COUNT-i){
return {i, i+x};
}
x-=COUNT-i;
}
return {-1, -1};
}
vector<int> vv;
int n;
vector<int> idx;
CartesianTree tree;
int l, r, bl, br;
int l_bs, r_bs;
int send_count;
void fake_SendA(bool y){
++send_count;
SendA(y);
}
int tl, tr;
pair<int, int> pl, pr;
int get_pos(int x){
if (pl.first==-1 || x<pl.first-pr.first+1) return pr.first+x;
return pl.second+(x-(pl.first-pr.first+1));
}
int get_len(){
return pr.second-pr.first+1-max(0, pl.second-pl.first-1);
}
int dep, id;
pair<int, int> find(){
dep=0, id=1;
tl=0, tr=n-1;
while (dep<13 && tl<tr){
int mid=(tl+tr)>>1;
if (r<=mid) tr=mid, id<<=1;
else if (l>=mid+1) tl=mid+1, id<<=1, id|=1;
else break;
++dep;
}
l_bs=0, r_bs=tr-tl;
pl={-1, -1}, pr={tl, tr};
return {dep, id-(1<<dep)};
}
void InitA(int _n, int _l, int _r){
n=_n, l=_l, r=_r;
auto t=find();
if (t.first<=1) fake_SendA(0), fake_SendA(0), fake_SendA(t.first);
else for (int i=3; i>=0; --i) fake_SendA((t.first+2)>>i&1);
for (int i=0; i<t.first; ++i) fake_SendA(t.second>>i&1);
}
void ReceiveA(bool x){
vv.push_back(x);
if (l_bs>=r_bs || send_count==18 || dep==13){
if (dep==13){
int array_len=tr-tl+1;
if ((int)vv.size()==array_len*2){
tree.build(vv);
for (int i=tl; i<=tr; ++i) idx.push_back(i);
}
return;
}
int num=l_bs;
int lg=__lg(num*2-1);
int array_len=1+r_bs+1-l_bs;
if (!l_bs) --array_len;
int len=array_len*2+(pl.first!=-1)*lg;
if ((int)vv.size()==len){
int min_id=-1;
if (l_bs){
min_id=0;
for (int i=0; i<lg; ++i) min_id|=vv[i]<<i;
min_id+=pl.first;
vv.erase(vv.begin(), vv.begin()+lg);
}
tree.build(vv);
for (int i=pr.first; i<=pr.second; ++i){
if (i==min_id) idx.push_back(min_id);
if (l_bs && pl.first<=i && i<=pl.second) continue;
idx.push_back(i);
}
}
}else{
int num=get_len();
int lg=__lg(num*2-1);
if ((int)vv.size()==lg){
int mid=(l_bs+r_bs)>>1;
int ql=0;
for (int i=0; i<lg; ++i) ql|=vv[i]<<i;
ql=get_pos(ql);
int qr=ql+mid;
fake_SendA(ql<=l && r<=qr);
if (ql<=l && r<=qr) r_bs=mid, pr={ql, qr};
else l_bs=mid+1, pl={ql, qr};
vv.clear();
}
}
}
int Answer(){
return idx[tree.lca(
lower_bound(idx.begin(), idx.end(), l)-idx.begin(),
upper_bound(idx.begin(), idx.end(), r)-idx.begin()-1
)];
}
} // namespace
void InitA(int N, int L, int R) {
Anna::InitA(N, L, R);
}
void ReceiveA(bool x) {
Anna::ReceiveA(x);
}
int Answer() {
return Anna::Answer();
}
#include "Bruno.h"
#include <vector>
#include <bits/stdc++.h>
using namespace std;
namespace Bruno{
const int SIZE=1384, COUNT=723;
struct SparseTable{
int n, lg;
vector<int> a;
vector<vector<pair<int, int>>> st;
void build(int _n, const vector<int> &_a){
n=_n; a=_a;
lg=0;
while ((1<<lg)<=n) ++lg;
st.assign(lg, vector<pair<int, int>>(n, {0, 0}));
for (int i=0; i<n; ++i) st[0][i]={a[i], i};
for (int k=1; k<lg; ++k){
for (int i=0; i+(1<<k)-1<n; ++i){
st[k][i]=min(st[k-1][i], st[k-1][i+(1<<(k-1))]);
}
}
}
int get(int l, int r){
assert(l<=r);
int k=__lg(r-l+1);
return min(st[k][l], st[k][r-(1<<k)+1]).second;
}
};
struct CartesianTree{
int n;
vector<int> left, right, par, dep;
vector<int> a;
SparseTable st;
vector<int> bin;
int root;
void gen_binary(){
bin.clear();
auto dfs=[&](auto &&self, int u) -> void {
if (left[u]!=-1) self(self, left[u]);
bin.push_back(0);
if (right[u]!=-1) self(self, right[u]);
bin.push_back(1);
};
dfs(dfs, root);
}
void dfs_dep(int u){
if (left[u]!=-1) dep[left[u]]=dep[u]+1, dfs_dep(left[u]);
if (right[u]!=-1) dep[right[u]]=dep[u]+1, dfs_dep(right[u]);
}
void build(int _n, const vector<int> &_a){
n=_n, a=_a;
st.build(n, a);
left.assign(n, -1);
right.assign(n, -1);
par.assign(n, -1);
dep.assign(n, 0);
auto dfs=[&](auto &&self, int l, int r) -> int {
if (l>r) return -1;
if (l==r) return l;
int m=st.get(l, r);
left[m]=self(self, l, m-1);
right[m]=self(self, m+1, r);
if (left[m]!=-1) par[left[m]]=m;
if (right[m]!=-1) par[right[m]]=m;
return m;
};
root=dfs(dfs, 0, n-1);
gen_binary();
dfs_dep(root);
}
int lca(int u, int v){
while (dep[u]<dep[v]) v=par[v];
while (dep[u]>dep[v]) u=par[u];
while (u!=v) u=par[u], v=par[v];
return u;
}
void build(const vector<int> &_bin){
bin=_bin;
n=(int)bin.size()/2;
vector<int> match(n*2);
stack<int> st;
for (int i=0; i<n*2; ++i){
if (bin[i]==0) st.push(i);
else match[st.top()]=i, match[i]=st.top(), st.pop();
}
left.assign(n, -1);
right.assign(n, -1);
par.assign(n, -1);
dep.assign(n, 0);
int cnt=0;
auto dfs=[&](auto &&self, int l, int r) -> int {
if (l>r) return -1;
int m=match[r];
int tl=self(self, l, m-1);
int u=cnt++;
int tr=self(self, m+1, r-1);
left[u]=tl, right[u]=tr;
if (left[u]!=-1) par[left[u]]=u;
if (right[u]!=-1) par[right[u]]=u;
return u;
};
root=dfs(dfs, 0, n*2-1);
dfs_dep(root);
}
};
int encode(pair<int, int> x){
int ans=0;
for (int i=0; i<x.first; ++i) ans+=COUNT-i;
return ans+(x.second-x.first);
}
pair<int, int> decode(int x){
for (int i=0; i<COUNT; ++i){
if (x<COUNT-i){
return {i, i+x};
}
x-=COUNT-i;
}
return {-1, -1};
}
int n;
vector<int> a;
vector<int> vv;
int cnt;
int bl, br;
int dep, id;
int sz_dep;
vector<pair<int, int>> v;
CartesianTree tree;
void InitB(int _n, vector<int> _a){
n=_n; a=_a;
}
int tl, tr;
void find(){
int cdep=0, cid=1;
tl=0, tr=n-1;
while (cdep<dep){
int mid=(tl+tr)>>1;
if (!(id>>(dep-cdep-1)&1)) tr=mid, cid<<=1;
else tl=mid+1, cid<<=1, cid|=1;
++cdep;
}
}
int l_bs, r_bs;
void send(int x, int num){
int lg=__lg(num*2-1);
for (int i=0; i<lg; ++i) SendB(x>>i&1);
}
pair<int, int> pl, pr;
int get_pos(int x){
if (pl.first==-1 || x<=pl.first) return x-pr.first;
return pl.first-pr.first+1+x-pl.second;
}
int get_len(){
return pr.second-pr.first+1-max(0, pl.second-pl.first-1);
}
bool check=0;
void ReceiveB(bool y){
vv.push_back(y);
++cnt;
if ((int)vv.size()==2){
if (vv[0]==0 && vv[1]==0) sz_dep=3;
else sz_dep=4;
}
if ((int)vv.size()==sz_dep){
if (sz_dep==3) dep=vv[2];
else{
for (int i=0; i<4; ++i) dep|=vv[3-i]<<i;
dep-=2;
}
}
if ((int)vv.size()==sz_dep+dep){
for (int i=0; i<dep; ++i) id|=vv[sz_dep+i]<<i;
id+=1<<dep;
find();
if (dep==13){
vector<int> val;
for (int i=tl; i<=tr; ++i){
val.push_back(a[i]);
}
tree.build(val.size(), val);
tree.gen_binary();
for (int i:tree.bin) SendB(i);
return;
}
int pos=(tl+tr)>>1;
int l=pos, r=pos;
while (1){
v.emplace_back(l, r);
if (l==tl && r==tr) break;
if (l==tl || (r<tr && a[r+1]>a[l-1])) ++r;
else --l;
}
l_bs=0, r_bs=(int)v.size()-1;
pl={-1, -1}, pr={tl, tr};
if (l_bs<r_bs){
int mid=(l_bs+r_bs)>>1;
send(get_pos(v[mid].first), get_len());
}
if (l_bs>=r_bs || cnt==18){
SparseTable st; st.build(n, a);
int min_id=-1;
if (l_bs){
min_id=st.get(pl.first, pl.second);
send(min_id-pl.first, l_bs);
}
vector<int> val;
for (int i=v[r_bs].first; i<=v[r_bs].second; ++i){
if (i==min_id) val.push_back(a[i]);
if (l_bs && pl.first<=i && i<=pl.second) continue;
val.push_back(a[i]);
}
tree.build(val.size(), val);
tree.gen_binary();
for (int i:tree.bin) SendB(i);
}
check=1;
}
if (check && (int)vv.size()>sz_dep+dep){
int mid=(l_bs+r_bs)>>1;
if (y) r_bs=mid, pr=v[mid];
else l_bs=mid+1, pl=v[mid];
if (l_bs>=r_bs || cnt==18){
SparseTable st; st.build(n, a);
int min_id=-1;
if (l_bs){
min_id=st.get(pl.first, pl.second);
send(min_id-pl.first, l_bs);
}
vector<int> val;
for (int i=v[r_bs].first; i<=v[r_bs].second; ++i){
if (i==min_id) val.push_back(a[i]);
if (l_bs && pl.first<=i && i<=pl.second) continue;
val.push_back(a[i]);
}
tree.build(val.size(), val);
tree.gen_binary();
for (int i:tree.bin) SendB(i);
}else{
int mid=(l_bs+r_bs)>>1;
send(get_pos(v[mid].first), get_len());
}
}
}
} // namespace
void InitB(int N, std::vector<int> P) {
Bruno::InitB(N, P);
}
void ReceiveB(bool y) {
Bruno::ReceiveB(y);
}
