#include <bits/stdc++.h>
#include "prize.h"
using namespace std;
int nr[] = {1, 2, 5, 26, 677};
int vmx = 0, vpos = 0;
const int bp = 5;
int getpos (int l, int r) {
int mid = (l + r) / 2;
for (int i = 0; i <= mid; i++){
if (mid + i <= r) {
vector <int> q = ask(mid + i);
if (q[0] + q[1] == vmx) return mid + i;
}
else if (mid - i >= l) {
vector <int> q = ask(mid - i);
if (q[0] + q[1] == vmx) return mid - i;
}
}
assert(0);
}
int brute(int l, int r) {
for (int i = l; i <= r ; i++){
vector <int> q = ask(i);
if (q[0] + q[1] == 0) return i;
}
return -1;
}
int solve (int l, int r, int ps) { // assume ps is vmx
vector <int> q = ask(ps);
if (q[0] <= bp) {
int k = brute(l, ps - 1);
return (k == -1 ? solve(ps + 1, r, getpos(ps + 1, r)) : k);
}
if (q[1] <= bp) {
int k = brute(ps + 1, r);
return (k == -1 ? solve(l, ps - 1, getpos(l, ps - 1)) : k);
}
return max(solve(l, ps - 1, getpos(l, ps - 1)), solve(ps + 1, r, getpos(ps + 1, r)));
}
int find_best(int n) {
vector <pair <int, int> > p;
for (int i = 0; i < min(50, n); i++){
vector <int> k = ask(i);
if (k[0] + k[1] > vmx) {
vpos = i;
vmx = k[0] + k[1];
}
}
return solve(1, n, vpos);
}
