#include "prize.h"
#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;
#define X first
#define Y second
const int MXN = 2e5+5;
int loli;
pii cache[MXN];
pii query(int i) {
if(cache[i].X!=-1) return cache[i];
vector<int> tmp = ask(i);
cache[i] = {tmp[0], tmp[1]};
if(cache[i].X+cache[i].Y==0) throw i;
return cache[i];
}
void rec(int l, int r, int cl, int cr) {
if(l>r) return;
for(int i=0; i<=r-l; i++) {
int mid=(l+r)>>1, ml=mid-(i>>1), mr = mid+((i+1)>>1);
mid = (i&1) ? mr : ml;
pii x = query(mid);
if(x.X+x.Y==loli) {
int ccl = (i&1) ? mr-ml : 0, ccr = (i&1) ? 0 : mr-ml;
if(x.X-ccl>cl) rec(l, ml-1, cl, ccl+x.Y);
if(x.Y-ccr>cr) rec(mr+1, r, x.X+ccr, cr);
return;
}
}
}
int find_best(int n) {
fill(cache, cache+n, pii(-1, -1));
try {
int pos=0;
for(int i=0; i<480 && i<n; i++) {
pii x = query(i);
if(x.X+x.Y>loli) {
loli = x.X+x.Y;
pos = i;
}
}
rec(pos, n-1, pos, 0);
}
catch(int ans) {
return ans;
}
return 0;
}
