#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#define pb push_backs
using namespace std;
vector<int> ask(int i);
int ans = -1;
int s;
int N;
vector<vector<int>> cache;
vector<int> cask(int m) {
if(m<=-1) return vector<int>(2,s);
if(m>=N) return vector<int>(2,0);
if(cache[m]==vector<int>(2,-1)) cache[m]=ask(m);
return cache[m];
}
bool chk(int l, int r) {
return (cask(l-1)[1]-cask(r)[1] > 0);
}
void bs(int l, int r) {
if(!chk(l, r)) return; //se l'intervallo è vuoto niente
if (ans!=-1) return; //se ans già trovata niente
int m = (l+r)/2;
auto v = cask(m); //query
if (v[0]+v[1]==0) {ans=m; return;} //se sol, fine
if(l==r) return; //
if (v[0]+v[1]<=s) {bs(l, m); bs(m+1, r); return;}
s=v[0]+v[1];
if (v[0]>0) bs(l, m);
if (v[1]>0) bs(m+1, r);
}
int find_best(int n) {
cache.resize(n, vector<int>(2,-1));
N=n;
// int i = 0; vector<int> k;
// do{k=ask(i++);} while(k[0]+k[1]<sqrt(n) and i<425);
s=sqrt(n);
bs(0, n);
return ans;
}
