#include <bits/stdc++.h>
using namespace std;
typedef long long llo;
#define a first
#define b second
#define pb push_back
#include "prize.h"
vector<int> pre[2000001];
pair<int,int> ma={-1,-1};
int ans;
vector<int> ask2(int i){
if(pre[i].size()>0){
return pre[i];
}
pre[i]=ask(i);
return pre[i];
}
void run(int l,int r,int aa,int bb){
if(aa+bb==ma.a){
return ;
}
if(l>r){
return;
}
//cout<<l<<":"<<r<<":"<<aa<<":"<<bb<<endl;
int mid=(l+r)/2;
int xx=0;
for(int i=mid;i>=l;i--){
vector<int> res=ask2(i);
if(res[0]+res[1]==ma.a){
if(i>l){
run(l,i-1,aa,res[1]);
}
if(mid<r){
run(mid+1,r,res[0]+xx,bb);
}
return;
}
xx++;
}
if(mid<r){
run(mid+1,r,aa+xx,bb);
}
}
int find_best(int n) {
for(int i=0;i<min(500,n);i++){
vector<int> res=ask2(i);
if(res[0]+res[1]>ma.a){
ma={res[0]+res[1],i};
}
/*if(ma.a>100){
break;
}*/
}
run(0,n-1,0,0);
for(int i=0;i<n;i++){
if(pre[i].size()>0){
if(pre[i][0]+pre[i][1]==0){
return i;
}
}
}
return 0;
}
