#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=480;
map<ll,vector<int>>memo;
ll N, ans=0;
bool enc=0;
vector<int>cons(ll x)
{
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)
{
vector<int>q=cons(x);
ll cant=q[0]+q[1];
cant=N-cant;
if(cant*cant+1>N)
return 1;
return 0;
}
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 (mid >= l) {
solve(l, mid, il, cons(mid)[0]);
solve((l + r) / 2 + 1, r, cons(mid)[0]+abs(mid-((l + r) / 2)), ir);
}
}
int find_best(int n) {
ll a=0, i, b=n-1;
N=n;
for(i=0; i<MAXM; i++)
{
if(lolip(i))
{
a=i;
break;
}
}
for(i=n-1; i>=n-MAXM; i--)
{
if(lolip(i))
{
b=i;
break;
}
}
solve(a,b,ask(a)[0],ask(b)[0]);
return ans;
}
