#include "prize.h"
#include <iostream>
#include <algorithm>
#include <cmath>
#include <ctime>
#include <cstdlib>
#include <vector>
#include <unistd.h>
#include <cassert>
using namespace std;
const int maxn=2e5+5;
const int cap=1000;
int sum;
bool asked[maxn];
int uk;
int nadji(int L, int D, int vall, int vald){
int mid=(L+D)/2;
vector < int > v={-1, -1};
while(mid<D && v[0]+v[1]!=sum){
if(!asked[mid]){
uk++;
v=ask(mid);
asked[mid]=1;
if(!v[0] && !v[1]){
return mid;
}
}
mid++;
}
if(v[0]+v[1]!=sum){
mid=(L+D)/2;
while(mid>=L && v[0]+v[1]!=sum){
if(!asked[mid]){
uk++;
v=ask(mid);
asked[mid]=1;
if(!v[0] && !v[1]){
return mid;
}
}
mid--;
}
if(v[0]+v[1]!=sum){
return -1;
}
uk--;
mid++;
}
else{
uk--;
mid--;
}
assert(uk<cap);
int br=-1;
if(v[0]-vall){
br=nadji(L, mid, vall, v[1]);
if(br!=-1){
return br;
}
}
if(v[1]-vald){
br=nadji(mid+1, D, v[0], vald);
}
return br;
}
int find_best(int n){
srand(time(NULL));
vector < int > v;
int pos;
for(int i=0; i<450; i++){
pos=rand()%n;
v=ask(pos);
if(!v[0] && !v[1]){
return pos;
}
sum=max(v[0]+v[1], sum);
}
int a=nadji(0, n, 0, 0);
assert(a!=-1);
return a;
}
