#include "prize.h"
#include <bits/stdc++.h>
using namespace std;
/*********************************************************************************************************************/
int find_best(int n) {
int left =0,middle = n/2, right = n-1;
int numleft = 0, numright = 0;//left and right from range
int curtotal = INT_MAX;
int cnt = 0;
while(true){
int numl, numr; //left and right from query
vector<int> res = ask(middle);
numl = res[0], numr = res[1];
if(numl == 0 && numr == 0)
return middle;
if(numl + numr < curtotal){
numleft = 0, numright = 0;
curtotal = numl + numr;
left = 0, middle = n/2, right = n-1;
// cout << "NEW TOTAL: "<<curtotal<<endl;
}
numl -= numleft;
numr -= numright;
//cout <<"("<< left <<", "<<middle<<", "<<right<<")";
//cout << ":\t"<<numleft <<", "<<numright<<", "<<numl<<", "<<numr;
int lhole = (middle - left) - numl +1;
int rhole = (right - middle) - numr +1;
//cout << ";\t"<<lhole<<", "<<rhole<<endl;
if( (lhole< rhole && numl > 0) || numr == 0){
right = middle -1;
middle = middle - lhole;
numright += numr;
}
else{
left = middle + 1;
middle = middle + rhole;
numleft +=numl;
}
cnt++;
if(cnt == 7) break;
}
return 0;
}
/*********************************************************************************************************************/
