#include "prize.h"
#include<bits/stdc++.h>
using namespace std;
int x;
map<int,int> m;
int solve(int l, int r, int ly, int ry){
if (ly+ry == x || r < l) return -1;
int mid = (l+r)/2;
int fm = mid;
vector<int> a;
while (mid <= r){
a = ask(mid);
if (a[0]+a[1] == 0) return mid;
if (a[0]+a[1] == x) break;
mid++;
}
return max(solve(l, fm-1, ly, a[1]+(mid-fm)), solve(mid+1, r, a[0], ry));
}
int find_best(int n) {
for (int i=0; i<500; i++){
vector<int> a = ask(i);
if (a[0]+a[1] == 0) return i;
m[a[0]+a[1]]++;
}
x = m.rend()->first;
return solve(500, n-1, 500-m[x], 0);
}
