#include "prize.h"
#include<bits/stdc++.h>
#define ll int
#define pb push_back
#define mp make_pair
#define ld long double
#define F first
#define S second
#define pii pair<ll,ll>
using namespace :: std;
const ll maxn=2e5+500;
const ll inf=1e9+900;
vector<ll> ansS[maxn];
ll mx=0;
vector<ll> ASK(ll x){
if(ansS[x].size())return ansS[x];
ansS[x]=ask(x);
mx=max(mx,ansS[x][0]+ansS[x][1]);
return ansS[x];
}
ll N;
ll bild(ll l,ll r,ll L,ll R){
l=max(l,0);
r=min(r,N);
if(l>=r)return -1;
if(L+R==mx)return -1;
ll mid=(l+r)/2;
for(ll i=mid;i<r;i++){
vector<ll> vec=ASK(i);
if(vec[0]+vec[1]==mx){
ll XX=bild(l,mid,L,vec[1]+(mid-i));
if(XX!=-1)return XX;
XX=bild(i+1,r,vec[0],R);
if(XX!=-1)return XX;
return -1;
}else{
if(vec[0]+vec[1]==0)return i;
}
}
return bild(l,mid,L,R+(r-mid));
}
int find_best(int n) {
N=n;
if(n<=5000){
for(ll i=0;i<n;i++){
vector<ll> vec=ask(i);
if(vec[0]+vec[1]==0)return i;
}
}
for(ll i=0;i<440;i++){
vector<ll> ans=ASK(i);
if(ans[0]+ans[1]==0)return i;
}
return bild(0,n,0,0);
}
