#include "prize.h"
#include<bits/stdc++.h>
using namespace std;
typedef int ll;
typedef pair<ll, ll> pll;
ll ans = -1, info[200200];
pll query_answer[200200];
pll do_ask(ll x){
if(!info[x]) {
vector<ll> v = ask(x);
query_answer[x] = {v[0], v[1]};
info[x] = 1;
}
return query_answer[x];
}
void rec(ll a, ll b, ll k, ll left, ll right, ll tot){
if(a > b || k <= 0 || ans != -1) return;
ll mid = (a + b) / 2, i = mid;
auto[l, r] = do_ask(mid);
if(a == b && (l + r) != 0) return;
for(; i <= b && (l + r) < tot; i++) {
auto[this_l, this_r] = do_ask(i);
l = this_l, r = this_r;
if(l + r == 0) {ans = i; return;}
}
ll cnt = i - mid;
if(i == b+1) {
i = mid;
for(; i >= a && (l + r) < tot; i--) {
auto[this_l, this_r] = do_ask(i);
l = this_l, r = this_r;
if(l + r == 0) {ans = i; return;}
}
if(i == a-1) return;
rec(a, i-1, l - left, left, tot - l, tot);
}
else{
rec(a, mid-1, l - left, left, tot - l, tot);
rec(i+1, b, r - right, tot - r, right, tot);
}
}
int find_best(int n) {
ll tot = 0;
for(ll i = 0; i <= sqrt(n) + 1; i++){
auto[x, y] = do_ask(i);
if(x == 0 && y == 0) return i;
tot = max(tot, (x + y));
}
rec(0, n-1, tot, 0, 0, tot);
return ans;
}
