#include "bits/stdc++.h"
#include "prize.h"
//#define int long long
#define all(v) v.begin() , v.end()
#define sz(a) (int)a.size()
using namespace std;
const int S = 100;
const int S2 = 20;
int L = -1 , suf = -1;
vector<int> Cache;
map<int,vector<int>> dp;
vector<int> Ask(int i){
if(dp.count(i)) return dp[i];
return dp[i]=ask(i);
}
int ask_all(int l,int r){
for(int i=l;i<=r;i++){
vector<int> x = Ask(i);
if(x[0]+x[1]==0) return i;
if(x[1]==suf) Cache=x;
else suf--;
}
return -23;
}
/*int Learn(int l,int r){
if(l==r){
auto u = Ask(l);
if(u[0]+u[1]==0) return l;
if(u[0]+u[1]==Cache[0]+Cache[1]) Cache=u;
return -1;
}
if()
int BL = (int)sqrtl(r-l+1);
auto x = ask(l+BL-1);
}*/
int find_best(int n){
if(n<=1000) return ask_all(0,n-1);
for(int i=0;i<=500;i++){
vector<int> x = Ask(i);
if(x[0]+x[1]==0) return i;
if(L==-1) Cache=x;
else if(x[0]+x[1]>=Cache[0]+Cache[1]) Cache=x;
}
suf=Cache[1];
L=500;
while(L+S<n){
vector<int> x = Ask(L+S);
if(x[0]+x[1]==0) return L+S;
if(suf==x[1]){
L+=S;
Cache=x;
continue;
}
int p = L;
while(p+S2<L+S){
p+=S2;
vector<int> u = Ask(p);
if(u[0]+u[1]==0) return p;
if(suf==u[1]) Cache=u;
else{
int xd = ask_all(p-S2,p);
if(xd!=-23) return xd;
}
}
int xd = ask_all(p,L+S);
if(xd!=-23) return xd;
L+=S;
}
return ask_all(L,n-1);
}
