#include "prize.h"
#include "bits/stdc++.h"
using namespace std;
#ifdef duc_debug
#include "bits/debug.h"
#else
#define debug(...)
#endif
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
int rand(int l, int r) {
assert(l <= r);
return uniform_int_distribution<int> (l, r)(rng);
}
int find_best(int n) {
vector<pair<int, int>> range;
int mx = 0;
for(int ite = 0; ite < 10; ++ite) {
int p = rand(0, n - 1);
vector<int> cur_ask = ask(p);
mx = max(mx, cur_ask[0] + cur_ask[1]);
}
vector<int> spec;
for(int i = 0; i < n; ++i) {
vector<int> cur_ask = ask(i);
if(cur_ask[0] + cur_ask[1] != mx) {
spec.push_back(i);
continue;
}
int l = i + 1, r = n - 1, nxt = i;
while(l <= r) {
int mid = (l + r) >> 1;
vector<int> he = ask(mid);
if(he == cur_ask) {
nxt = mid;
l = mid + 1;
} else {
r = mid - 1;
}
}
// debug(i, nxt);
i = nxt;
}
// debug((int)spec.size());
for(auto i:spec) {
vector<int> cur_ask = ask(i);
if(cur_ask[0] == 0 and cur_ask[1] == 0) {
return i;
}
}
return -1;
}
