#include "prize.h"
#include <bits/stdc++.h>
using namespace std;
vector<int> ask_res(int i){
vector<int> rep = ask(i);
//if (i != 7) cout << "query " << i << " " << rep[0] << " " << rep[1] << endl;
return rep;
}
int find_best(int n) {
int dernier = n/2;
vector<int> resDernier = ask_res(dernier);
while (resDernier[0] != 0 || resDernier[1] != 0){
int badLeft = dernier - resDernier[0], badRight = n - resDernier[1] - dernier - 1;
//cout << "iter " << badLeft << " " << badRight << " " << resDernier[0] << " " << resDernier[1] << endl;
if ((badLeft < badRight && resDernier[0] != 0) || resDernier[1] == 0){
vector<int> resCur = resDernier;
// cout << "ylo" << endl;
while (resCur[0] + resCur[1] >= resDernier[0] + resDernier[1]){
dernier -= resCur[0];
resCur = ask_res(dernier);
}
resDernier = resCur;
}
else {
vector<int> resCur = resDernier;
while (resCur[0] + resCur[1] >= resDernier[0] + resDernier[1]){
// if (dernier != 7)
// cout << "ans " << resCur[0] + resCur[1] << " " << resDernier[0] + resDernier[1] << endl;
dernier += resCur[1];
resCur = ask_res(dernier);
}
// cout << "fini" << endl;
resDernier = resCur;
}
// resDernier = resCur;
}
return dernier;
//return 0;
}
