#include "prize.h"
using namespace std;
using pii = pair<int, int>;
#define X first
#define Y second
const int MN = 200000, MC = 500;
int cnt, tot, chk[MN], dia;
pii dat[MN];
pii get(int x){
if(chk[x]) return dat[x];
chk[x] = 1;
vector<int> v = ask(x);
dat[x] = pii(v[0], v[1]);
if(v[0] + v[1] == 0) dia = x;
tot = max(tot, v[0] + v[1]);
return dat[x];
}
void pre(int s, int e){
if(cnt == MC) return;
int m = (s + e) / 2;
get(m); cnt++;
if(s == e) return;
pre(s, m);
pre(m + 1, e);
}
void dnc(int s, int e, int lc, int mc, int rc){
if(mc == 0) return;
if(s == e){
get(s);
return;
}
int m = (s + e) / 2;
int mmc = 0;
for(int i = m; i >= s; i--){
pii t = get(i);
if(t.X + t.Y == tot){
mmc += t.X - lc;
break;
}
mmc++;
}
dnc(s, m, lc, mmc, rc + mc - mmc);
dnc(m + 1, e, lc + mmc, mc - mmc, rc);
}
int find_best(int n) {
pre(0, n - 1);
dnc(0, n - 1, 0, tot, 0);
return dia;
}
