#include "prize.h"
#include<bits/stdc++.h>
using namespace std;
mt19937 rng(time(nullptr));
const int N=2e5+5;
int cnt=0;
int n;
int ans=-1;
vector<vector<int>> mem(N);
int mx;
int le,ri;
vector<int> ask2(int x){
if(mem[x].empty()){
assert(++cnt<=1e4);
mem[x]=ask(x);
}
return mem[x];
}
void bsearch(int l,int r){
int m=(l+r)/2;
int idx=m;
auto res=ask2(idx);
int val=res[0]+res[1];
if(val==0)ans=idx;
if(l==r)return;
while(val<mx&&idx+1<=r){
idx++;
res=ask2(idx);
val=res[0]+res[1];
if(val==0)ans=idx;
}
if(val==mx){
if(res[0]-le){
if(l<=m-1){
ri+=res[1];
bsearch(l,m-1);
ri-=res[1];
}
}
if(res[1]-ri){
if(idx+1<=r){
le+=res[0];
bsearch(idx+1,r);
le-=res[0];
}
}
}else{
idx=m-1;
res=ask2(idx);
val=res[0]+res[1];
if(val==0)ans=idx;
while(val<mx&&idx-1>=l){
idx--;
res=ask2(idx);
val=res[0]+res[1];
if(val==0)ans=idx;
}
if(val==mx){
if(res[0]-le){
if(l<=idx-1){
ri+=res[1];
bsearch(l,idx-1);
ri-=res[1];
}
}
}
}
}
int find_best(int _n) {
n=_n;
for(int i=0;i*i<=n;i++){
auto res=ask2(i);
mx=max(mx,res[0]+res[1]);
}
for(int i=0;i*i<n;i++){
auto res=ask2(i);
if(res[0]+res[1]==mx)continue;
if(res[0]+res[1]==0)return i;
}
bsearch(0,n-1);
return ans;
}
