#include "prize.h"
#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (r); ++x)
typedef long long ll;
typedef std::pair<int,int> pii;
using namespace std;
jmp_buf jb;
int ans;
const int N = 200'010;
pii table[N];
int n;
pii query(int i) {
if (table[i] != pii{})
return table[i];
auto tmp = ask(i);
if (tmp[0] + tmp[1] == 0) {
ans = i;
longjmp(jb, 1);
}
return (table[i] = {tmp[0], tmp[1]});
}
void solve(int l, int r, int cl, int cr, int tot)
{
if (cl + cr == tot)
return;
int m = (l+r)/2;
Loop (i,0,r-l) {
int pos = i%2? m-i/2-1: m+i/2;
auto [x, y] = query(pos);
if (x + y > tot) {
solve(0, n, 0, 0, x + y);
assert(!"unreachable");
}
if (x + y < tot)
continue;
solve(l, pos, cl, y, tot);
solve(pos+1, r, x, cr, tot);
return;
}
}
int find_best(int n) {
::n = n;
if (setjmp(jb))
return ans;
auto [x, y] = query(n/2);
solve(0, n, 0, 0, x+y);
assert(!"unreachable");
}
