#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);
int br=0;
int pos;
vector < int > v;
do{
pos=rand()%(D-L)+L;
if(!asked[pos]){
v=ask(pos);
asked[pos]=1;
if(!v[0] && !v[1]){
return pos;
}
}
br++;
}while(br<200 && v[0]+v[1]!=sum);
if(v[0]+v[1]!=sum){
for(int i=L; i<D; i++){
if(!asked[i]){
asked[i]=1;
v=ask(i);
if(!v[0] && !v[1]){
return i;
}
}
}
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){
assert(0);
srand(time(NULL));
vector < int > v;
int pos;
for(int i=0; i<10; i++){
pos=rand()%n;
v=ask(pos);
if(!v[0] && !v[1]){
return pos;
}
sum=max(sum, v[0]+v[1]);
}
int a=nadji(0, n, 0, 0);
assert(a!=-1);
return a;
}
