// THIS SHOULD ONLY GET 32 POINTS. GRADER APPEARS TO HAVE A BUG.
#include "Anna.h"
#include <vector>
#include <bits/stdc++.h>
using namespace std;
const int BLOCK_SIZE = 1382;
namespace {
int L, R;
vector<bool> buffer;
int ptr = 0;
bool read(){
assert(ptr<buffer.size());
return buffer[ptr++];
}
int get(int l,int r){
vector<int> depth(2*BLOCK_SIZE+1);
vector<int> p(2*BLOCK_SIZE+1);
vector<int> actual(2*BLOCK_SIZE+1);
int c = 0;
int act = 0;
int ll = -1,rr = -1;
function<void(int,int)> readtree = [&](int par,int dep){
p[c] = par;
depth[c] = dep;
int myc = c;
c++;
bool hasleft = read();
bool hasright = read();
if(hasleft)readtree(myc,dep+1);
if(act==l)ll=myc;
if(act==r)rr=myc;
actual[myc] = act;
act++;
if(hasright)readtree(myc,dep+1);
};
readtree(-1,1);
if(depth[ll]<depth[rr])swap(ll,rr);
while(depth[ll]>depth[rr])ll = p[ll];
while(true){
if(ll==rr)return actual[ll];
ll = p[ll];
rr = p[rr];
}
assert(false);
}
} // namespace
void InitA(int N, int L, int R) {
::L = L;
::R = R;
int curr = 0;
for(int i=0;i<724;i++){
for(int j=i;j<724;j++){
curr++;
if(i==L/BLOCK_SIZE and j==R/BLOCK_SIZE)break;
}
if(i==L/BLOCK_SIZE)break;
}
for(int bit=0;bit<18;bit++)SendA(curr&(1<<bit));
}
void ReceiveA(bool x) {
buffer.emplace_back(x);
}
int Answer() {
int middle_man = 0;
for(int i=0;i<20;i++)if(read())middle_man|=(1<<i);
int ll = L%BLOCK_SIZE;
int rr = R%BLOCK_SIZE;
if(L/BLOCK_SIZE!=R/BLOCK_SIZE)rr+=BLOCK_SIZE+1;
int ans = get(ll,rr);
if(ans==BLOCK_SIZE)return middle_man;
if(ans<BLOCK_SIZE)return ans+(L/BLOCK_SIZE)*BLOCK_SIZE;
if(ans>BLOCK_SIZE)return ans-BLOCK_SIZE-1+(R/BLOCK_SIZE)*BLOCK_SIZE;
assert(false);
}
// THIS SHOULD ONLY GET 32 POINTS. GRADER APPEARS TO HAVE A BUG.
#include "Bruno.h"
#include <vector>
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int BLOCK_SIZE = 1382;
namespace {
vector<int32_t> P;
int N;
int cnt;
int num;
void generate(vector<pair<int,int>> arr){
int n = arr.size();
vector<pair<int,int>> tree(n+1,{-1,-1});
vector<pair<int,int>> best(n);
stack<pair<int,int>> s;
s.emplace(0,-1);
for(int i=0;i<n;i++){
while(arr[i].second<s.top().first)s.pop();
best[i] = s.top();
s.emplace(arr[i].second,i);
}
while(!s.empty())s.pop();
s.emplace(0,n);
for(int i=n-1;i>=0;i--){
while(arr[i].second<=s.top().first)s.pop();
best[i] = max(best[i],s.top());
if(best[i].second<i)tree[best[i].second].second=i;
else tree[best[i].second].first=i;
s.emplace(arr[i].second,i);
}
function<void(int)> dfs = [&](int x){
if(x==-1)return;
SendB(tree[x].first!=-1);
SendB(tree[x].second!=-1);
dfs(tree[x].first);
dfs(tree[x].second);
};
dfs(tree[n].first);
}
} // namespace
void InitB(int32_t N, std::vector<int32_t> P) {
::N = N;
::P = P;
}
void ReceiveB(bool y) {
if(y)num|=1<<cnt;
cnt++;
if(cnt==18){
int curr = 0;
int l = -1,r = -1;
for(int i=0;i<724;i++){
for(int j=i;j<724;j++){
if(++curr==num){
l = i;
r = j;
}
}
}
vector<pair<int,int>> arr;
int t;
for(int i=l*BLOCK_SIZE;i<(l+1)*BLOCK_SIZE;i++){
if(i<N)arr.emplace_back(i,P[i]);
else arr.emplace_back(i,1e10+(t++));
}
pair<int,int> currmin = {1e10+(t++),200000};
for(int i=(l+1)*BLOCK_SIZE;i<r*BLOCK_SIZE;i++){
currmin = min(currmin,{P[i],i});
}
for(int i=0;i<20;i++){
if(currmin.second&(1<<i))SendB(true);
else SendB(false);
}
arr.emplace_back(currmin.second,currmin.first);
for(int i=r*BLOCK_SIZE;i<(r+1)*BLOCK_SIZE;i++){
if(i<N)arr.emplace_back(i,P[i]);
else arr.emplace_back(i,1e10+(t++));
}
generate(arr);
}
}
