#include "prize.h"
#include <bits/stdc++.h>
using namespace std;
int res = -1;
int c = 0;
int find_best(int n) {
int current = 0;
int val = ask(current)[1];
int rk = val;
while(true){
int l = 0;
int r = n;
while(r-l > 0){
int m = (r+l)/2;
c++;
if(c == 10000)while(true);
vector<int> ans = ask(m);
int v = ans[0]+ans[1];
if(v == 0){
res = m;
break;
}
if(ans[1] == val && v ==rk){
l = m;
}else if(v == rk){
r = m;
}
if(v != rk){
r = m;
}
}
if(res !=-1)break;
if(l == current){
current++;
c++;
if(c == 10000)while(true);
vector<int> ans = ask(current);
int v = ans[0]+ans[1];
if(v == 0){
res = current;
break;
}
rk = v;
val = ans[1];
}else{
current = l;
c++;
if(c == 10000)while(true);
vector<int> ans = ask(current);
int v = ans[0]+ans[1];
if(v == 0){
res = current;
break;
}
rk = v;
val = ans[1];
}
}
return res;
}
