#include <bits/stdc++.h>
using namespace std;
#include "prize.h"
mt19937 ayahya(chrono::high_resolution_clock().now().time_since_epoch().count());
int ans = -1;
map<int,vector<int>> mp;
inline vector<int> query(int x){
if (mp.count(x)) return mp[x];
return mp[x]=ask(x);
}
inline int querys(int x){
return query(x)[0]+query(x)[1];
}
void solve(int l, int r){
if (l==r){
if (querys(l)==0) ans=l;
return;
}
if (querys(l)<querys(r)){
if (querys(l)==0){
ans=l;
return;
}
solve(l+1,r);
return;
}
else if (querys(r)<querys(l)){
if (querys(r)==0){
ans=r;
return;
}
solve(l,r-1);
return;
}
if (query(l)[0]==query(r)[0]) return;
int mid = l+(r-l)/2;
solve(l,mid);
solve(mid,r);
}
int find_best(int n) {
solve(0,n-1);
assert(ans!=-1);
return ans;
}
