#include <bits/stdc++.h>
#include "prize.h"
using namespace std;
vector< vector< int > > memo;
int TOT = 0;
vector< int > ASK(int a){
if(memo[a][0] != -1) return memo[a];
else{
TOT++;
assert(TOT < 10000);
return memo[a] = ask(a);
}
}
int find_best(int n) {
int poppy_index = -1;
int poppy_tot = 0;
vector< vector< int > > rem(n+1, vector< int > (2));
memo.resize(n, vector< int >(2,-1));
for(int i = 0; i < min(n,446); i++){
vector< int > query = ASK(i);
rem[query[0] + query[1]] = query;
if(query[0] + query[1] >= poppy_tot){
poppy_tot = query[0] + query[1];
poppy_index = i;
}else if(query[0] + query[1] == 0){
return i;
}
}
int curr = poppy_index+1;
while(curr < n){
vector< int > query = ASK(curr);
rem[query[0] + query[1]] = query;
if(query[0] + query[1] == 0) return curr;
while(query[0] + query[1] != poppy_tot){
curr++;
query = ASK(curr);
rem[query[0] + query[1]] = query;
if(query[0] + query[1] == 0) return curr;
}
int left = curr+1;
int right = n-1;
while(left < right){
int mid = (left+right)/2;
vector< int > Q = ASK(mid);
if(Q[0] + Q[1] == 0) return mid;
if(Q[0] + Q[1] == poppy_tot && Q[0] - query[0] == 0){
left = mid+1;
rem[Q[0] + Q[1]] = Q;
}
else if(Q[0] + Q[1] == poppy_tot && Q[0] - query[0] > 0) right = mid-1;
else if(Q[0] + Q[1] != poppy_tot && Q[0] - rem[Q[0] + Q[1]][0] == 0){
left = mid+1;
rem[Q[0] + Q[1]] = Q;
}
else right = mid;
}
curr = left;
}
return 0;
}
