#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, idx = mid, d = 0;
pll range = {mid, mid};
auto[l, r] = do_ask(mid);
if(a == b && (l+r) != 0) return;
while(l + r < tot){
auto[this_l, this_r] = do_ask(idx);
l = this_l, r = this_r;
if(l + r == tot) break;
if(l == 0 && r == 0) {ans = idx; return;}
if(idx <= mid) idx = mid + (++d), range.second = idx;
else idx = mid-d, range.first = idx;
}
auto[idx_l, idx_r] = range;
ll cnt = idx_r - idx_l;
if(l > left) rec(a, idx_l-1, l - left - (idx == idx_r ? cnt : 0), left, tot - (l - left - (idx == idx_r ? cnt : 0)) - left, tot);
if(r > right) rec(idx_r+1, b, r - right - (idx == idx_l ? cnt : 0), tot - (r - right - (idx == idx_l ? cnt : 0)) - right, right, tot);
}
int find_best(int n) {
ll tot = 0;
for(ll i = 0; i <= sqrt(n); 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;
}
