#include "prize.h"
#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<ll, ll> pll;
typedef pair<ull, ull> pull;
typedef pair<int, int> pii;
typedef pair<ld, ld> pld;
int ans = -1;
int curval;
vector<int> dp[200009];
int qu = 0;
vector<int> q(int x){
if(dp[x].size())
return dp[x];
++qu;
if(qu >= 10000){
for(int i = 0;; ++i)
if(dp[i].empty()){
ans = i;
return {1, 1};
}
}
return dp[x] = ask(x);
}
void binsearch(int l, int r, int lval, int rval){
int cnt = curval-lval-rval;
if(cnt == 0 || l > r || ans != -1)
return;
int mid = (l+r)/2;
for(int i = 0; (mid-i) >= l || (mid+i) <= r; ++i){
int extra = 0;
if(ans != -1 || cnt <= 0) return;
if((mid-i) >= l){
int id = (mid-i);
vector<int> res = q(id);
if(ans != -1) return;
if(res[0]+res[1] == curval){
binsearch(l, id-1, lval, res[1]);
binsearch(max(mid+i,mid+1), r, res[0]+extra, rval);
return;
}
else if(res[0]+res[1] == 0){
ans = id;
return;
}
else{
--cnt;
++extra;
}
}
if(ans != -1 || cnt <= 0) return;
if(i != 0 && (mid+i) <= r){
int id = mid+i;
vector<int> res = q(id);
if(ans != -1) return;
if(res[0]+res[1] == curval){
binsearch(l, mid-i-1, lval, res[1]+extra);
binsearch(id+1, r, res[0], rval);
return;
}
else if(res[0]+res[1] == 0){
ans = id;
return;
}
else{
--cnt;
++extra;
}
}
}
}
int find_best(int n) {
srand(time(NULL));
int times = 10;
while(times--){
vector<int> res = q(rand()%n);
curval = max(res[0], res[1]);
}
binsearch(0, n-1, 0, 0);
assert(ans != -1 && q(ans)[0] == 0 && q(ans)[1] == 0);
return ans;
}
