#include "prize.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ii pair<int,int>
#define fi first
#define se second
#define rep(x,s,e) for (auto x=(s)-((s)>(e));x!=(e)-((s)>(e));((s)<(e)?x++:x--))
#define all(x) (x).begin(),(x).end()
#define sz(x) (int) (x).size()
mt19937 rng(42069);
const int CHECK=400;
ii memo[200005];
ii get(int i){
if (memo[i]!=ii(-1,-1)) return memo[i];
auto temp=ask(i);
return memo[i]=ii(temp[0],temp[1]);
}
int mx;
vector<int> good;
void dnc(int l,int r,int i,int j){
//rep(x,0,100000000) ;
//cout<<l<<" "<<r<<" "<<i<<" "<<j<<endl;
if (r<l) return;
if (i==j) return;
int m=l+r>>1;
int m2=m;
while (m2<=r && get(m2).fi+get(m2).se!=mx){
good.push_back(m2);
m2++;
}
if (m2>r) dnc(l,m-1,i,j-(m2-m));
else{
auto temp=get(m2);
dnc(l,m-1,i,temp.fi-(m2-m));
dnc(m2+1,r,temp.fi,j);
}
}
int find_best(int n) {
memset(memo,-1,sizeof(memo));
vector<int> pos;
rep(x,0,n) pos.push_back(x);
rep(x,0,n) swap(pos[x],pos[rng()%(x+1)]);
rep(x,0,min(n,CHECK)){
auto temp=get(pos[x]);
mx=max(mx,temp.fi+temp.se);
}
dnc(0,n-1,0,mx);
//for (auto &it:good) cout<<it<<" "; cout<<endl;
for (auto &it:good){
if (get(it)==ii(0,0)) return it;
}
return -1;
}
