#include <bits/stdc++.h> #define pb push_backs using namespace std; vector<int> ask(int i); int ans = -1; int s = 1e9; int N; int tt; 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]; assert(s==tt);// in teoria dopo la prima volta sempre uguale 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=cask(i++);} while(k[0]+k[1]<sqrt(n) and i<500); tt=k[0]+k[1]; s=sqrt(n); bs(0, n); return ans; }