#include "prize.h"
#include <bits/stdc++.h>
using namespace std;
map<int,vector<int>>mp;
vector<int>kask(int n){
if(mp.find(n)!=mp.end()){
return mp[n];
}
return mp[n]=ask(n);
}
int find_best(int n) {
mp.clear();
int cutoff = 0;
int lef = 0;
int ind = -1;
for(int i = 0; i < min(n,480); i++) {
vector<int> res = kask(i);
if(res[0] + res[1] == 0)
return i;
if(cutoff<res[0]+res[1]) {
cutoff=res[0]+res[1];
ind=i;
lef=res[0];
}
}
while(1){
int lo = ind;
int hi = min(n-1,lo+1023);
while(lo<hi){
int mid = (lo+hi+1)/2;
vector<int>res = kask(mid);
if(res[0]+res[1]==0){
return mid;
}
if(res[0]==lef&&res[0]+res[1]==cutoff){
lo=mid;
}
else{
hi=mid-1;
}
}
ind=lo;
while(++ind<n){
vector<int>res = kask(ind);
lef=res[0];
if(res[0]+res[1]==cutoff){
break;
}
if(res[0]+res[1]==0){
return ind;
}
}
if(ind==n){
break;
}
}
return -1;
}
