#include "prize.h"
#include<vector>
#include<map>
#include<utility>
#include<cassert>
#define MAXN 200005
using namespace std;
map<int, int> Q[MAXN];
int slv(int l, int r) {
if (l == r) {return(l);}
int mid = (l + r) >> 1;
vector<int> res = ask(mid);
int tot = res[0] + res[1], resL=-1, resR=-1;
if (tot == 0) {return(mid);}
auto ptr1 = Q[tot].insert({mid, res[0]}).first, ptr2=ptr1;
if ((ptr1 == Q[tot].begin() || (*(--ptr1)).second != res[0]) && res[0]) {
resL = slv(l, mid-1);
}
ptr1 = ptr2;
if ((++ptr1 == Q[tot].end() || (*ptr1).second != res[1]) && res[1]) {
resR = slv(mid+1, r);
}
return(resL != -1 ? resL : resR);
}
int find_best(int n) {
return(slv(0, n-1));
}
