#include <bits/stdc++.h>
#define ll long long
#define sz(x) int(x.size())
#define forn(i,n) for(i=0; i<n; i++)
#define all(x) x.begin(),x.end()
#define pb push_back
#define mp make_pair
#define fr first
#define se second
using namespace std;
vector<int> ask(int i);
const int MAXM=447;
map<ll,vector<int>>memo;
ll ans=0;
int N;
bool enc=0;
int maxi=0;
vector<int>cons(ll x)
{
if(enc)
return {N,N};
auto it=memo.find(x);
if(it==memo.end())
memo[x]=ask(x);
if(memo[x][0]+memo[x][1]==0)
{
enc=1;
ans=x;
}
return memo[x];
}
bool lolip(ll x)
{
int sumx = cons(x)[0] + cons(x)[1];
if(sumx==0) enc=1, ans=x;
return sumx < maxi;
}
void solve(ll l, ll r, ll il, ll ir)
{
if(il==ir||enc)
return;
if(l==r)
{
cons(l);
return;
}
ll mid=(l+r)/2;
while(!enc && mid>=l && lolip(mid)) mid--;
if(enc) return;
if(mid>=l){
solve(l,mid,il,cons(mid)[0]);
if(enc) return;
solve((l+r)/2+1,r,cons(mid)[0]+abs(((l+r)/2)-mid),ir);
}
}
int find_best(int n) {
ll i;
N=n;
maxi=0;
for(i=0; i<min(MAXM,n); i++){
int s = cons(i)[0]+cons(i)[1];
maxi = max(maxi,s);
if(enc) break;
}
int a=0, b=n-1;
while(!enc && a<n && cons(a)[0]+cons(a)[1]!=maxi) a++;
while(!enc && b>=0 && cons(b)[0]+cons(b)[1]!=maxi) b--;
if(!enc) solve(a,b,cons(a)[0],cons(b)[0]);
return ans;
}
