#include <bits/stdc++.h>
#include "prize.h"
using namespace std;
using Query = vector<int>;
int find_best(int n) {
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 = ask(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 = ask(0);
if (valid(L)) {
return 0;
}
Query R = ask(n - 1);
if (valid(R)) {
return n - 1;
}
dfs(0, n - 1, L, R);
return ans;
}
