#include <bits/stdc++.h>
#include "prize.h"
using namespace std;
using Query = vector<int>;
int find_best(int n) {
vector<Query> value(n);
auto query = [&](int i) -> Query {
if (value[i].empty()) value[i] = ask(i);
return value[i];
};
auto valid = [&](Query x) {
return x[0] + x[1] == 0;
};
int ans = -1;
function<void(int, int, Query, Query)> dfs = [&](int l, int r, Query L, Query R) {
if (l + 1 >= r || ans != -1 || L == R) {
return;
}
int mid = (l + r) >> 1;
Query M = query(mid);
if (valid(M)) {
ans = mid;
return;
}
if (L[0] + L[1] == R[0] + R[1] && L[0] + L[1] != M[0] + M[1] && L[1] - R[1] == 1) {
return;
}
dfs(l, mid, L, M), dfs(mid, r, M, R);
};
Query L = query(0);
if (valid(L)) {
return 0;
}
Query R = query(n - 1);
if (valid(R)) {
return n - 1;
}
dfs(0, n - 1, L, R);
return ans;
}
