#include "prize.h"
#include <bits/stdc++.h>
using namespace std;
mt19937_64 rng(random_device{}());
#define my_random(l,r) uniform_int_distribution<int>(l,r)(rng)
#define my_shuffle(...) shuffle(__VA_ARGS__,rng)
map<int, vector<int>> cache;
map<int, set<int>> S;
int n;
int mx;
vector<int> ASK(int x) {
if(x==-1) return {0, n};
if(x==n) return {n, 0};
if(not cache.contains(x)) cache[x] = ask(x);
S[cache[x][0] + cache[x][1]].insert(x);
return cache[x];
}
void search(int a, int b) {
if(a>b) return;
int m1=(a+b)>>1, m2=m1;
auto v=ASK(m1);
while(a<=m1 && ASK(m1)[0] + ASK(m1)[1] < mx) {
m1--;
}
if(a<m1 && ASK(a-1)[0]<ASK(m1)[0]) {
search(a, m1-1);
}
if(ASK(m2)[1]>ASK(b+1)[1]) {
search(m2+1, b);
}
}
int find_best(int _n) {
n = _n;
for(int i=0; i<200; ++i) {
auto v=ASK(my_random(0, n-1));
mx = max(mx, v[0]+v[1]);
}
search(0, n-1);
for(auto [x, y] : S) {
cerr << x << ": ";
for(auto e : y) cerr << e << ' ';
cerr << endl;
}
assert(S.begin()->first == 0);
return *(S.begin()->second.begin());
}
