#include <bits/stdc++.h>
#include "prize.h"
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
#define fi first
#define se second
#define mp make_pair
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
map<int,pii> res;
pii get(int x){
if(res.count(x)) return res[x];
vector<int> g = ask(x);
res[x] = mp(g[0], g[1]);
return mp(g[0],g[1]);
}
int n;
int solve(int li, int ri){
if(li > ri) return -1;
pii sa = get(li);
pii sb = get(ri);
if(sa.fi + sa.se == 0) return li;
if(sb.fi + sb.se == 0) return ri;
if(ri - li <= 1) return -1;
if(sa.fi + sa.se != sb.fi + sb.se){
if(sa.fi + sa.se > sb.fi + sb.se){
return solve(li, ri - 1);
}
else{
return solve(li + 1, ri);
}
}
if(sa.se - sb.se == 0){
return -1;
}
int mid = (li + ri) / 2;
int qa = solve(li, mid);
if(qa != -1) return qa;
return solve(mid + 1, ri);
}
int find_best(int _n) {
n = _n;
return solve(0, n - 1);
}
