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