#include "prize.h"
using namespace std;
#define vi vector<int>
int biggestCt = -1;
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;
bool change = false;
if (sum > biggestCt) {
biggestCt = sum;
}
if (sum != biggestCt) continue;
int ans = solve(mid+1, r, res[0], change ? -1 : numRight);
if (ans != -1) return ans;
return solve(l, (l+r)/2-1, change ? -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;
bool change = false;
if (sum > biggestCt) {
biggestCt = sum;
}
if (sum != biggestCt) continue;
int ans = solve(l, mid-1, change ? -1 : numLeft, res[1]);
if (ans != -1) return ans;
break;
}
return -1;
}
int find_best(int n) {
return solve(0, n-1, 0, 0);
}
