#include "prize.h"
#include<bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;
#define f first
#define s second
#define sz(x) (int) (x).size()
#define all(x) (x).begin(), (x).end()
mt19937 rng((uint32_t) chrono::steady_clock::now().time_since_epoch().count());
int find_best(int n) {
int queries = 0;
auto query = [&](int id) -> vector<int> {
queries++;
//assert(queries <= 9990);
return ask(id);
};
if (n <= 7) {
for(int i = 0; i < n; i++) {
std::vector<int> res = query(i);
if(res[0] + res[1] == 0)
return i;
}
}
const int TIMES = 30;
int lim = 0;
for (int i = 0; i < TIMES; i++) {
vector<int> q = query(rng() % n);
lim = max(lim, q[0] + q[1]);
}
Tree<int> rem; // not identified
Tree<int> done;
for (int i = 0; i < n; i++) {
rem.insert(i);
}
auto purge = [&](int id) {
rem.erase(id);
done.insert(id);
};
auto destroy = [&](int id, int t) {
if (t == 0) {
while (sz(rem) && *rem.begin() < id) purge(*rem.begin());
} else {
while (sz(rem) && *rem.rbegin() > id) purge(*rem.rbegin());
}
};
while (true) {
bool ok = false;
int lo = 0;
int hi = sz(rem) - 1;
while (hi - lo > 1) {
int mid = (lo + hi) / 2;
int id = *rem.find_by_order(mid);
vector<int> q = query(id);
if (q[0] + q[1] == 0) {
return id;
} else if (q[0] + q[1] < lim) {
purge(id);
for (int t = 0; t < 2; t++) {
if (q[t] == 0) destroy(id, t);
}
ok = true;
break;
} else {
q[0] -= done.order_of_key(id);
q[1] -= sz(done) - done.order_of_key(id);
if (q[0] && q[1]) {
if (q[0] > q[1]) hi = mid - 1;
else lo = mid + 1;
} else if (q[0]) {
hi = mid - 1;
} else {
lo = mid + 1;
}
}
}
if (ok) continue;
int id = *rem.find_by_order(lo);
vector<int> q = query(id);
if (q[0] + q[1] < lim) {
if (q[0] + q[1] == 0) {
return id;
} else {
purge(id);
for (int t = 0; t < 2; t++) {
if (q[t] == 0) destroy(id, t);
}
}
} else {
id = *rem.find_by_order(hi);
q = query(id);
assert(q[0] + q[1] < lim);
if (q[0] + q[1] == 0) {
return id;
} else {
purge(id);
for (int t = 0; t < 2; t++) {
if (q[t] == 0) destroy(id, t);
}
}
}
}
return 0;
}
