#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){
if(l > r)return -1;
int mid = (l+r)/2;
int i,j;
for(i=mid+1;i<=r;i++){
vector<int>res = ask(i);
if(!res[0] && !res[1])return i;
else if(!res[1]){
i = r;
break;
}
else if(res[0] + res[1] > lim)break;
}
for(j=mid;j>=l;j--){
vector<int>res = ask(j);
if(!res[0] && !res[1])return j;
else if(!res[0]){
j = l;
break;
}
else if(res[0] + res[1] > lim)break;
}
int c = solve(i+1,r);
if(c != -1)return c;
c = solve(l,j-1);
return c;
}
int find_best(int n) {
if(n<=0){
for(int i=0;i<n;i++){
vector<int>res = ask(i);
if(!res[0] && !res[1])return i;
}
}
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
return solve(0,n-1);
}
