#include "prize.h"
#include<bits/stdc++.h>
using namespace std;
int mxsum = 0;
map<int,vector<int>> mem;
vector<int> myask(int i){
if(mem.count(i)) return mem[i];
mem[i] = ask(i);
return mem[i];
}
bool ismx(vector<int> ans){
int s = ans[0] + ans[1];
return s == mxsum;
}
int find_best(int N) {
for(int i = 0; i < min(N, 711); i++){
vector<int> ans = myask(i);
int s = ans[0] + ans[1];
if(ans[0] + ans[1] == 0){
return i;
}
if(s > mxsum) mxsum = s;
}
int idx = 0;
while(1){
vector<int> ori;
while(1){
vector<int> ans = myask(idx);
if(ismx(ans)) {
ori = ans;
break;
}
if(ans[0] + ans[1] == 0){
return idx;
}
idx++;
}
int l = idx, r = N - 1;
while(l < r){
int m = (l + r) / 2;
auto ans = myask(m);
if(ans[0] + ans[1] == 0){
return m;
}
if(ans[1] == ori[1]){
l = m + 1;
}else if(ans[1] < ori[1]){
r = m - 1;
}
}
if(myask(l)[1] == ori[1]){
idx = l + 1;
}else{
idx = l;
}
}
return -1;
}
