#include "prize.h"
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
using pii = pair<int, int>;
#define forn(i, n) for(int i=0; i<(int)n; ++i)
#define PB push_back
#define F first
#define S second
const int MAXN = 200010;
int n, can=-1, offset[MAXN], sum;
pii info[MAXN];
vector<int> values, obt;
pii myask(int i){
if(info[i].F==-1){
vector<int> ret = ask(i);
info[i] = {ret[0], ret[1]};
}
return info[i];
}
bool dfs(int l, int r, int x, int y){
if(l==r || x+y==sum) return true;
int mid = (l+r)>>1, mn=n+2, mx=-1, lx, ly, cnt=0, lst=mid;
forn(i, r-l){
int pt = mid + offset[i];
lst=pt;
mn = min(mn, pt);
mx = max(mx, pt);
pii res = myask(values[pt]);
lx=res.F, ly=res.S;
if(res.F + res.S > sum){
sum = res.F + res.S;
can = values[pt];
return false;
}
if(res.F + res.S < sum) obt.PB(values[pt]);
if(res.F + res.S == sum) break;
++cnt;
}
int x2=lx, y2=ly;
if(lst>mid) y2+=cnt;
else x2+=cnt;
if(!dfs(l, mn, x, y2)) return false;
if(!dfs(mx+1, r, x2, y)) return false;
return true;
}
int find_best(int N) {
n=N;
values.resize(n);
forn(i, n) info[i]={-1, -1}, values[i]=i;
forn(i, n) offset[i]=(i&1? -((i+1)>>1) : ((i+1)>>1));
while(values.size()>1){
sum = -1;
while(!dfs(0, values.size(), 0, 0)){
obt.clear();
if(sum==0) return can;
}
swap(values, obt);
obt.clear();
sort(values.begin(), values.end());
}
return values.front();
}
