#include "prize.h"
#include <iostream>
#include <vector>
#include <random>
#define ll long long
using namespace std;
ll f;
vector <int> R;
void solve(ll l, ll r, ll ql, ll qr) {
if (l > r || ql + qr == R[0] + R[1]) return;
ll mid = (l+r)/2;
for (int i=mid; i<=r; ++i) {
auto u = ask(i);
if (!u[0] && !u[1]) {
f = i;
return;
}
else if (u[0]+u[1] == R[0]+R[1]) {
solve(l, mid-1, ql, u[1]+(i-mid));
if (f != -1) return;
solve(i+1, r, u[0], qr);
return;
}
}
solve(l, mid-1, ql, qr+(r-mid+1));
}
int find_best(int n) {
f = -1;
random_device rd;
mt19937 mt(rd());
R = {-1, -1};
for (int i=0; i<10; ++i) {
ll id = mt() % n;
auto u = ask(id);
if (u[0]+u[1] > R[0]+R[1]) swap(u, R);
}
solve(0, n-1, 0, 0);
return f;
}
