#include "prize.h"
#include <bits/stdc++.h>
using namespace std;
int lim = 0;
#define sz(a) (int)(a.size());
int solve(int l,int r,int lf = 0,int rg = 0){
//cout<<l<<" "<<r<<'\n';
if(l > r)return -1;
int mid = (l+r)/2;
int i,j;
int cl = 0,cr = 0;
for(i=mid;i<=r;i++){
vector<int>res = ask(i);
if(!res[0] && !res[1])return i;
else if(res[0] + res[1] > lim){
if(!(res[1]-rg)){ //nothing to find on right side
i = r;
break;
}
cl = res[0];
cr = res[1];
break;
}
}
if(i == mid)j = i;
else{
for(j=mid;j>=l;j--){
vector<int>res = ask(j);
if(!res[0] && !res[1])return j;
else if(res[0] + res[1] > lim){
if(!(res[0]-lf)){ //nothing to find on left side
i = r;
break;
}
cr = res[1];
break;
}
}
}
int c = solve(i+1,r,cl,rg);
if(c != -1)return c;
c = solve(l,j-1,lf,cr);
return c;
}
int find_best(int n) {
lim = 1;
for(int i = 2;i<=n;i++){
int c = i * i + 1;
if(c + i + 1<=n)lim = i+1;
else break;
} //biggest value possible
int ans = solve(0,n-1);
return ans;
}
