#include "prize.h"
#include <bits/stdc++.h>
using namespace std;
map<int, vector<int>> M, Li;
vector<int> self_ask(int i){
if(!M.count(i)) M[i] = ask(i); vector<int> r = M[i];
Li[r[0] + r[1]].push_back(i);
return r;
}
vector<int> b;
bool failed = false;
void solve(int l, int r, int cc, int lc, int rc){
if(l > r || lc == rc) return;
int L = (l + r) / 2, R = (l + r) / 2 + 1, F = 0;
int c; vector<int> a;
while(true){
c = F ? R++ : L--; F ^= 1;
a = self_ask(c);
if(a[0] + a[1] > cc){
failed = true; cc = a[0] + a[1];
return;
}
if(a[0] + a[1] == cc || R - L - 1 == rc - lc){
break;
}
}
if(c == L + 1){
solve(l, L, cc, lc, a[0]); if(failed) return;
solve(R, r, cc, a[0] + (R - L - 2), rc); if(failed) return;
}else{
solve(l, L, cc, lc, a[0] - (R - L - 2)); if(failed) return;
solve(R, r, cc, a[0], rc); if(failed) return;
}
}
int find_best(int n) {
int cc = 1;
do{
failed = false;
solve(0, n - 1, cc, 0, cc);
}while(failed);
for(auto [i, p] : M){
if(p[0] + p[1] == 0){
return i;
}
}
return -1;
}
