#include "Anna.h"
#include "bits/stdc++.h"
namespace {
#ifdef DEBUG
#include "../../debug.h"
#define debug(...) std::cerr << "A:" << __LINE__ << ":[" << #__VA_ARGS__ << "]:"; debug_out(__VA_ARGS__)
#else
#define debug(...) void(23)
#endif
int lg(int x) {
if (x <= 0) {
return 0;
}
return std::__lg(x);
}
int mode;
int counter = 0;
std::vector<int> buffer;
int N;
int L;
int R;
constexpr int LOG = 20;
constexpr int MAX_DEP = 13;
constexpr int ALICE_MAX = 18;
int l;
int r;
int d;
std::vector<int> path;
void build1() {
l = 0;
r = N - 1;
d = 0;
while (l != r && d != MAX_DEP) {
int mid = (l + r) >> 1;
if (R <= mid) {
path.emplace_back(0);
r = mid;
} else if (mid + 1 <= L) {
path.emplace_back(1);
l = mid + 1;
} else {
break;
}
d += 1;
}
debug(l, r, d);
debug(path);
if (d < 2) {
SendA(0);
SendA(0);
SendA(d);
counter += 3 + d;
for (int i = 0; i < d; ++i) {
SendA(path[i]);
}
} else {
for (int i = 0; i < 4; ++i) {
SendA((d + 2) >> (3 - i) & 1);
}
counter += 4 + d;
for (int i = 0; i < d; ++i) {
SendA(path[i]);
}
}
}
int lo;
int hi;
int mid;
int ls_lo;
int rs_lo;
int ls_hi;
int rs_hi;
void read() {
int dif = 0;
int len = lg(mid - lo);
if (len + 1 != int(buffer.size())) {
return;
}
for (int i = 0; i <= len; ++i) {
dif += buffer[i] << i;
}
int ls_mid = ls_lo - dif;
int rs_mid = ls_mid + mid;
debug(ls_lo, rs_lo);
debug(ls_hi, rs_hi);
debug(ls_mid, rs_mid);
debug(dif, len);
debug(lo, hi, mid);
debug();
if (ls_mid <= L && R <= rs_mid) {
ls_hi = ls_mid;
rs_hi = rs_mid;
hi = mid;
SendA(0);
} else {
ls_lo = ls_mid;
rs_lo = rs_mid;
lo = mid;
SendA(1);
}
mid = (lo + hi) >> 1;
buffer.clear();
counter += 1;
debug(counter);
}
void build2() {
int m = (l + r) >> 1;
lo = 0;
hi = r - l;
ls_lo = m;
rs_lo = m;
ls_hi = l;
rs_hi = r;
mid = (lo + hi) >> 1;
}
std::vector<int> ids;
} // namespace
void InitA(int N, int L, int R) {
::N = N;
::L = L;
::R = R;
build1();
if (d == MAX_DEP) {
for (int i = l; i <= r; ++i) {
ids.emplace_back(i);
}
mode = 2;
return;
}
build2();
mode = 0;
}
void ReceiveA(bool x) {
buffer.emplace_back(x);
if (mode == 0) {
read();
if (counter == ALICE_MAX) {
debug("ids");
mode = 1;
}
return;
}
if (mode == 1) {
if (int(buffer.size()) == LOG) {
debug(ls_lo, rs_lo);
debug(ls_hi, rs_hi);
int p = 0;
for (int i = 0; i < LOG; ++i) {
p += buffer[i] << i;
}
for (int i = ls_hi; i < ls_lo; ++i) {
ids.emplace_back(i);
}
ids.emplace_back(p);
for (int i = rs_lo + 1; i <= rs_hi; ++i) {
ids.emplace_back(i);
}
mode = 2;
buffer.clear();
}
return;
}
if (mode == 2) {
// do nothing
}
}
int Answer() {
// debug(ids);
std::vector<int> tree = buffer;
int p = 0;
std::vector<int> stk;
for (auto i : tree) {
if (ids[p] > R) {
break;
}
if (i == 0) {
stk.pop_back();
} else {
stk.emplace_back(ids[p]);
p += 1;
}
}
debug(stk);
assert(!stk.empty());
int ans = -1;
for (auto i : stk) {
if (i >= L) {
ans = i;
break;
}
}
debug(ans);
assert(L <= ans && ans <= R);
return ans;
}
#include "Bruno.h"
#include "bits/stdc++.h"
namespace {
#ifdef DEBUG
#include "../../debug.h"
#define debug(...) std::cerr << "B:" << __LINE__ << ":[" << #__VA_ARGS__ << "]:"; debug_out(__VA_ARGS__)
#else
#define debug(...) void(23)
#endif
int lg(int x) {
if (x <= 0) {
return 0;
}
return std::__lg(x);
}
int mode;
int counter = 0;
std::vector<int> buffer;
int N;
std::vector<int> P;
constexpr int LOG = 20;
constexpr int MAX_DEP = 13;
constexpr int ALICE_MAX = 18;
int l;
int r;
int d;
std::vector<int> path;
void build1() {
l = 0;
r = N - 1;
int p = 0;
while (l != r && p != d) {
int mid = (l + r) >> 1;
if (path[p] == 0) {
r = mid;
} else {
l = mid + 1;
}
p += 1;
}
debug(l, r, d);
}
int lo;
int hi;
int mid;
std::vector<int> ls;
std::vector<int> rs;
void send() {
int dif = ls[lo] - ls[mid];
int len = lg(mid - lo);
debug(ls[lo], rs[lo]);
debug(ls[hi], rs[hi]);
debug(ls[mid], rs[mid]);
debug(dif, len);
debug(lo, hi, mid);
debug();
for (int i = 0; i <= len; ++i) {
SendB(dif >> i & 1);
}
}
void build2() {
int m = (l + r) >> 1;
int ll = m;
int rr = m;
while (true) {
ls.emplace_back(ll);
rs.emplace_back(rr);
if (ll - 1 >= l) {
if (rr + 1 <= r) {
(P[ll - 1] > P[rr + 1] ? ll -= 1 : rr += 1);
} else {
ll -= 1;
}
} else {
if (rr + 1 <= r) {
rr += 1;
} else {
break;
}
}
}
lo = 0;
hi = r - l;
mid = (lo + hi) >> 1;
send();
}
std::vector<int> ids;
std::vector<int> create_cartesian_tree() {
std::vector<int> res;
std::vector<int> stk;
for (auto i : ids) {
while (!stk.empty() && P[stk.back()] > P[i]) {
res.emplace_back(0);
stk.pop_back();
}
res.emplace_back(1);
stk.emplace_back(i);
}
return res;
}
} // namespace
void InitB(int N, std::vector<int> P) {
::N = N;
::P = P;
mode = 0;
}
void ReceiveB(bool y) {
buffer.emplace_back(y);
if (mode == 0) {
debug(buffer);
if (int(buffer.size()) == 3 && buffer[0] == 0 && buffer[1] == 0) {
counter += 3;
d = buffer[2];
mode = 1;
buffer.clear();
} else if (int(buffer.size() == 4)) {
counter += 4;
d = 0;
for (int i = 0; i < 4; ++i) {
d += buffer[i] << (3 - i);
}
d -= 2;
mode = 1;
buffer.clear();
}
}
if (mode == 1) {
if (int(buffer.size()) == d) {
counter += d;
path.resize(d);
for (int i = 0; i < d; ++i) {
path[i] = buffer[i];
}
debug(path);
build1();
debug(l, r, d);
if (d == MAX_DEP) {
for (int i = l; i <= r; ++i) {
ids.emplace_back(i);
}
std::vector<int> tree = create_cartesian_tree();
for (int i = 0; i < int(tree.size()); ++i) {
SendB(tree[i]);
}
return;
}
build2();
mode = 2;
buffer.clear();
return;
}
}
if (mode == 2) {
counter += 1;
if (buffer[0] == 0) {
hi = mid;
} else {
lo = mid;
}
buffer.clear();
debug(counter);
if (counter == ALICE_MAX) {
debug(ls[lo], rs[lo]);
debug(ls[hi], rs[hi]);
for (int i = ls[hi]; i < ls[lo]; ++i) {
ids.emplace_back(i);
}
int p = std::min_element(P.begin() + ls[lo], P.begin() + rs[lo] + 1) - P.begin();
ids.emplace_back(p);
// debug(p);
for (int i = 0; i < LOG; ++i) {
SendB(p >> i & 1);
}
for (int i = rs[lo] + 1; i <= rs[hi]; ++i) {
ids.emplace_back(i);
}
debug(ids);
std::vector<int> tree = create_cartesian_tree();
for (int i = 0; i < int(tree.size()); ++i) {
SendB(tree[i]);
}
} else {
mid = (lo + hi) >> 1;
send();
}
}
}
