#include <bits/stdc++.h>
#include "prize.h"
using namespace std;
#define ll long long
#define SZ(x) (int) x.size()
const int N = 200'005;
vector<int> asked[N];
int cnt;
vector<int> get(int i) {
if (SZ(asked[i])) {
return asked[i];
}
cnt++;
assert(cnt <= 10'000);
return asked[i] = ask(i);
}
int solve(int l, int r) {
while (l <= r && get(l)[0] + get(l)[1] != get(r)[0] + get(r)[1]) {
vector<int> vl = get(l), vr = get(r);
if (vl[0] + vl[1] < vr[0] + vr[1]) {
if (vl[0] + vl[1] == 0) {
return l;
}
l++;
} else {
if (vr[0] + vr[1] == 0) {
return r;
}
r--;
}
}
if (l > r) return -1;
vector<int> vl = get(l), vr = get(r);
if (vl == vr) {
vector<int> v = get(l);
if (v[0] + v[1] == 0) {
return l;
}
return -1;
}
return max(solve(l, (l + r) / 2), solve((l + r) / 2 + 1, r));
}
int find_best(int n) {
return solve(0, n - 1);
}
