#include "prize.h"
#include <bits/stdc++.h>
using namespace std;
vector<int> dp[200002];
bool check(int med,int idx){
vector<int> res;
if(!dp[med].empty())res=dp[med];
else res=ask(med),dp[med]=res;
if(dp[idx].empty())dp[idx]=ask(idx);
return (dp[idx][0]==res[0]&&dp[idx][1]==res[1]);
}
int find_best(int n) {
/*for (int i = 29979; i < 29979+sqrt(n); ++i)
{
cerr<<ask(i)[0]<<" "<<ask(i)[1]<<"\n";
}*/
int s=sqrt(n);
int maxi=0,idx=0;
for (int i = 0; i < min(477,n); ++i)
{
dp[i]=ask(i);
if(dp[i][0]+dp[i][1]==0)return i;
if(dp[i][0]+dp[i][1]>=maxi)maxi=dp[i][0]+dp[i][1],idx=i;
}
for (int j = 477; j < n; j+=s)
{
//cerr<<j<<"a\n";
if(idx+s>=n)break;
while(idx<(j+s-1)){
int l=idx+1,r=j+s-1,ans=idx;
while(l<=r){
int med=(l+r)/2;
if(check(med,idx))ans=med,l=med+1;
else r=med-1;
if(med<n&&dp[med][0]+dp[med][1]==0)return med;
}
ans++;
while(ans<(j+s)){
vector<int> res;
if(!dp[ans].empty())res=dp[ans];
else res=ask(ans),dp[ans]=res;
if(dp[ans][0]+dp[ans][1]==0)return ans;
if(dp[ans][0]+dp[ans][1]>=maxi){
maxi=dp[ans][0]+dp[ans][1],idx=ans;
break;
}
ans++;
}
if(ans>=(j+s))idx=j+s;
}
/*cerr<<idx<<":idx\n";
cerr<<j<<" "<<j+s<<"---\n";*/
for (int i = idx; i < min(j+s,n); i++)
{
//cerr<<i<<"\n";
if(dp[i].empty())dp[i]=ask(i);
if(dp[i][0]+dp[i][1]==0)return i;
if(dp[i][0]+dp[i][1]>=maxi){maxi=dp[i][0]+dp[i][1];idx=i;break;}
}
}
//cerr<<idx<<"----\n";
for (int i = idx; i < n; ++i)
{
if(dp[i].empty())dp[i]=ask(i);
if(dp[i][0]+dp[i][1]==0)return i;
}
return 0;
}
