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