#include "prize.h"
using namespace std;
#define vi vector<int>
int biggestCt = 0;
int solve(int l, int r, int numLeft, int numRight) {
if (l > r) return -1;
if (numLeft + numRight == biggestCt) return -1;
for (int mid = (l+r)/2; mid <= r; mid++) {
vi res = ask(mid);
int sum = res[0] + res[1];
if (sum == 0) return mid;
if (sum != biggestCt) continue;
int ans = solve(mid+1, r, res[0], numRight);
if (ans != -1) return ans;
return solve(l, (l+r)/2-1, numLeft, res[1] + mid-(l+r)/2);
}
for (int mid = (l+r)/2-1; mid >= l; mid--) {
vi res = ask(mid);
int sum = res[0] + res[1];
if (sum == 0) return mid;
if (sum != biggestCt) continue;
int ans = solve(l, mid-1, numLeft, res[1]);
if (ans != -1) return ans;
break;
}
return -1;
}
int find_best(int n) {
for (int i = 0; i < min(n, 473); i++) {
vi res = ask(i);
if (res[0] + res[1] == 0) return i;
biggestCt = max(biggestCt, res[0] + res[1]);
if (biggestCt >= 15) break;
}
return solve(0, n-1, 0, 0);
}
