#include <bits/stdc++.h>
#include "prize.h"
using namespace std;
set<int> s[200200];
int ans[200200];
int solve(int l, int r) {
if (l > r) {
return -1;
}
int md = (l + r) >> 1;
vector<int> a = ask(md);
ans[md] = a[0];
int all = a[0] + a[1];
if (all == 0) {
return md;
}
auto it = s[all].insert(md).first;
if (it == s[all].begin() || ans[*prev(it)] != ans[md]) {
int cur = solve(l, md - 1);
if (~cur) return cur;
}
if (it == --s[all].end() || ans[*next(it)] != ans[md]) {
int cur = solve(md + 1, r);
if (~cur) return cur;
}
return -1;
}
int find_best(int n) {
return solve(0, n - 1);
}
