#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) {
if (n <= 7) {
for(int i = 0; i < n; i++) {
std::vector<int> res = ask(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 = ask(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);
}
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 = ask(id);
if (q[0] + q[1] == 0) {
return id;
} else if (q[0] + q[1] < lim) {
rem.erase(id);
done.insert(id);
ok = true;
break;
} else {
q[0] -= done.order_of_key(id);
q[1] -= sz(done) - done.order_of_key(id);
if (q[0]) {
hi = mid - 1;
} else {
lo = mid + 1;
}
}
}
if (ok) continue;
int id = *rem.find_by_order(lo);
vector<int> q = ask(id);
if (q[0] + q[1] < lim) {
if (q[0] + q[1] == 0) {
return id;
} else {
rem.erase(id);
done.insert(id);
}
} else {
id = *rem.find_by_order(hi);
q = ask(id);
assert(q[0] + q[1] < lim);
if (q[0] + q[1] == 0) {
return id;
} else {
rem.erase(id);
done.insert(id);
}
}
}
return 0;
}
