#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 = 30;
const int bp2 = 5000000;
int getpos (int l, int r) {
int mid = (l + r) / 2;
for (int i = 0; i <= mid + 2; i++){
if (mid + i <= r) {
vector <int> q = ask(mid + i);
if (q[0] + q[1] == vmx || q[0] + q[1] == 0) return mid + i;
}
if (mid - i >= l) {
vector <int> q = ask(mid - i);
if (q[0] + q[1] == vmx || q[0] + q[1] == 0) return mid - i;
}
}
return mid;
// 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) {
// cout << l << " " << r << " " << ps << "\n";
vector <int> q = ask(ps);
if (q[0] + q[1] == 0) return ps;
if (l >= r) return -1;
if (q[0] && q[0] <= bp && ps - l <= bp2) {
int k = brute(l, ps - 1);
return (k == -1 ? solve(ps + 1, r, getpos(ps + 1, r)) : k);
}
if (q[1] && q[1] <= bp && r - ps <= bp2) {
int k = brute(ps + 1, r);
return (k == -1 ? solve(l, ps - 1, getpos(l, ps - 1)) : k);
}
int rs = -1;
if (q[0] > q[1]){
rs = solve(l, ps - 1, getpos(l, ps - 1));
return (rs == -1 ? solve(ps + 1, r, getpos(ps + 1, r)): rs);
}
else {
rs = solve(ps + 1, r, getpos(ps + 1, r));
return (rs == -1 ? solve(l, ps - 1, getpos(l, ps - 1)): rs);
}
}
int find_best(int n) {
for (int i = 0; i < min(50, n); i++){
vector <int> k = ask(i);
if (k[0] + k[1] > vmx) {
vmx = k[0] + k[1];
}
}
// cout << getpos(0, n - 1);
return solve(0, n - 1, getpos(0, n - 1));
// vmx = 1;
// return solve(0, n-1, 3);
}
